首页 > 代码库 > POJ 3450 Corporate Identity KMP
POJ 3450 Corporate Identity KMP
题意:找所有字符串中的最长公共字串
解题思路:KMP+剪枝,因为如果我们知道前缀如果不满足条件,所有以这个开头的都不行。
解题代码:
1 // File Name: getnext.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 22时35分02秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 char str1[300]; 28 char str[4004][300]; 29 int next[305]; 30 void split(int x ,int y ) 31 { 32 int t = -1; 33 for(int i = x ;i <= y ;i ++) 34 { 35 str1[++t] = str[1][i]; 36 } 37 str1[++t] = ‘\0‘; 38 } 39 void getnext() 40 { 41 int len = strlen(str1); 42 next[0] = -1; 43 int k = -1; 44 int j = 0 ; 45 while(j <= len - 1) 46 { 47 if(k == -1 || str1[j] == str1[k]) 48 { 49 ++j; 50 ++k; 51 next[j] = k ; 52 } 53 else { 54 k = next[k]; 55 } 56 } 57 } 58 int kmp(int k) 59 { 60 int j = 0 ; 61 int i = 0 ; 62 int len = strlen(str1); 63 64 while(j < strlen(str[k])) 65 { 66 if(i == -1 || str1[i] == str[k][j]) 67 { 68 i ++ ; 69 j ++ ; 70 }else{ 71 i = next[i]; 72 } 73 if(i == len) 74 { 75 return 1; 76 } 77 } 78 return 0 ; 79 } 80 int n ; 81 char ans[100]; 82 int maxlen; 83 int solve(int x, int y) 84 { 85 split(x,y); 86 // puts(str1); 87 getnext(); 88 for(int i = 2 ;i <= n;i ++) 89 { 90 if(!kmp(i)) 91 { 92 return 0 ; 93 } 94 } 95 //puts(str1); 96 if(y - x + 1 > maxlen) 97 { 98 strcpy(ans,str1); 99 maxlen = y-x +1; 100 }101 else if(y -x +1 == maxlen)102 {103 if(strcmp(ans,str1) > 0)104 strcpy(ans,str1);105 }106 return 1;107 }108 int main(){109 while(scanf("%d",&n),n)110 {111 maxlen = 0 ; 112 int minlen = 1e9;113 for(int i = 1 ;i <= n;i ++)114 {115 scanf("%s",str[i]);116 if(strlen(str[i]) < minlen)117 {118 minlen = strlen(str[i]);119 }120 }121 for(int i = 0 ;i < strlen(str[1]) ;i ++)122 for(int j = i;j < strlen(str[1]) ;j ++)123 {124 if(!solve(i,j) || j-i+1 > minlen)125 {126 break;127 }128 }129 if(maxlen > 0)130 {131 puts(ans);132 }else {133 printf("IDENTITY LOST\n");134 }135 }136 return 0;137 }
POJ 3450 Corporate Identity KMP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。