pku3450 Corporate Identity &&pku3080 Blue Jeans（枚举+KMP)-白红宇

pku3450 Corporate Identity &&pku3080 Blue Jeans（枚举+KMP)

阅读量：5113 次

发布时间：2019-06-13

本文共 1837 字，大约阅读时间需要 6 分钟。

题意：求多个串的最长公共子串

pku3450用KMP算法

#include
     
      #include
      
       #include
       
        using namespace std;int nxt[210];char str[4010][210],s[210];int n,m;bool KMP(char *T,char *P){	memset(nxt,0,sizeof(nxt));	nxt[0]=-1;	int k=-1;	for(int q=1;q
        
         -1&& P[k+1]!=P[q])			k=nxt[k];		if(P[k+1]==P[q])			k++;		nxt[q]=k;	}	int j=-1,i=0;	while(T[i])	{		while(j>-1 && P[j+1]!=T[i])			j=nxt[j];		if(P[j+1]==T[i])			j++;		if(j+1==m)			return true;		i++;	}	return false;}int main(){	int t;	while(scanf("%d",&t)==1 && t)	{	   int l,min1=10000;       for(int i=0;i
         
          0)        printf("%s\n",s); 		else puts("IDENTITY LOST");    }  	return 0;}

pku3450用strstr（）函数

#include
     
      #include
      
       #include
       
        using namespace std;char str[4010][210],s[210];int n,m;int main(){	int t;	while(scanf("%d",&t)==1 && t)	{	   int l,min1=10000;       for(int i=0;i
        
         0)        printf("%s\n",s); 		else puts("IDENTITY LOST");    }  	return 0;}

pku3080

#include
     
      #include
      
       #include
       
        using namespace std;int nxt[100];char str[15][110],s[110];int n,m;bool KMP(char *T,char *P){	memset(nxt,0,sizeof(nxt));	nxt[0]=-1;	int k=-1;	for(int q=1;q
        
         -1&& P[k+1]!=P[q])			k=nxt[k];		if(P[k+1]==P[q])			k++;		nxt[q]=k;	}	int j=-1,i=0;	while(T[i])	{		while(j>-1 && P[j+1]!=T[i])			j=nxt[j];		if(P[j+1]==T[i])			j++;		if(j+1==m)			return true;		i++;	}	return false;}int main(){	int cas,t;	scanf("%d",&cas);	while(cas--)	{		scanf("%d",&n);	   int l,min1=10000;       for(int i=0;i
         
          =3)        printf("%s\n",s); 		else puts("no significant commonalities");    }  	return 0;}