題意:給你兩個字符串s1,s2,讓你求一個最大長度的子串t,t是s1的前綴,並且是s2的後綴,輸出t和t的長度,如果不存在,直接輸出0.
1、直接求next
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std; typedef long long LL; const int N=50005; const LL II=100000000; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); int next[2*N],len; char str[2*N],xh[N]; void getnext(char *p) { int j=0,k=-1; next[0]=-1; while(j<len)//len是p的長度 { if(k==-1||p[j]==p[k]) { j++; k++; next[j]=k; } else k=next[k]; } } int main() { int i,j,T; while(scanf("%s%s",str,xh)!=EOF) { int len1=strlen(str),len2=strlen(xh); len=len1+len2; strcat(str,xh); getnext(str); while(next[len]>len1||next[len]>len2) { len=next[len]; } str[next[len]]='\0'; if(next[len]==0) printf("0\n"); else printf("%s %d\n",str,next[len]); } return 0; } #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std; typedef long long LL; const int N=50005; const LL II=100000000; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); int next[2*N],len; char str[2*N],xh[N]; void getnext(char *p) { int j=0,k=-1; next[0]=-1; while(j<len)//len是p的長度 { if(k==-1||p[j]==p[k]) { j++; k++; next[j]=k; } else k=next[k]; } } int main() { int i,j,T; while(scanf("%s%s",str,xh)!=EOF) { int len1=strlen(str),len2=strlen(xh); len=len1+len2; strcat(str,xh); getnext(str); while(next[len]>len1||next[len]>len2) { len=next[len]; } str[next[len]]='\0'; if(next[len]==0) printf("0\n"); else printf("%s %d\n",str,next[len]); } return 0; }
2、KMP匹配,將s1作為模式串,將s2作為主串,直接kmp
#include <cstdio> #include <cstring> using namespace std; const int N = 50002; char str1[N]; char str2[N]; int next[N]; void get_next(int len_1); int kmp_search(int len_1, int len_2); int main() { int len; while(scanf("%s%s", str1, str2) != EOF) { int len_1 = strlen(str1); int len_2 = strlen(str2); get_next(len_1); len = kmp_search(len_1, len_2); if(len == 0) { printf("0\n"); } else { for(int i = 0; i < len; i++) { printf("%c", str1[i]); } printf(" %d\n", len); } } return 0; } void get_next(int len_1) { int i = 0; int j = -1; next[i] = -1; while(i < len_1) { if(j == -1 || str1[j] == str1[i]) { i++; j++; if(str1[i] == str1[j]) { next[i] = next[j]; } else { next[i] = j; } } else { j = next[j]; } } } int kmp_search(int len_1, int len_2) { int i = 0; int j = 0; while(i < len_2) { if(j == -1 || str1[j] == str2[i]) { i++; j++; } else { j = next[j]; } } if(j == -1) { return 0; } if(j == 0) { if(str1[0] == str2[len_2 - 1]) { return 1; } else { return 0; } } else { return j; } } #include <cstdio> #include <cstring> using namespace std; const int N = 50002; char str1[N]; char str2[N]; int next[N]; void get_next(int len_1); int kmp_search(int len_1, int len_2); int main() { int len; while(scanf("%s%s", str1, str2) != EOF) { int len_1 = strlen(str1); int len_2 = strlen(str2); get_next(len_1); len = kmp_search(len_1, len_2); if(len == 0) { printf("0\n"); } else { for(int i = 0; i < len; i++) { printf("%c", str1[i]); } printf(" %d\n", len); } } return 0; } void get_next(int len_1) { int i = 0; int j = -1; next[i] = -1; while(i < len_1) { if(j == -1 || str1[j] == str1[i]) { i++; j++; if(str1[i] == str1[j]) { next[i] = next[j]; } else { next[i] = j; } } else { j = next[j]; } } } int kmp_search(int len_1, int len_2) { int i = 0; int j = 0; while(i < len_2) { if(j == -1 || str1[j] == str2[i]) { i++; j++; } else { j = next[j]; } } if(j == -1) { return 0; } if(j == 0) { if(str1[0] == str2[len_2 - 1]) { return 1; } else { return 0; } } else { return j; } }