思路:kmp+next数组的应用
分析:
1 题目要求的是给定两个字符串s1 , s2找到s1的最长前缀等于s2的后缀
2 很明显就是next数组的应用,我们知道next[j] = len,表示的前j个字符里面前缀和后缀的最长匹配长度为len。那么我们只要合并两个字符串然后求next数组即可。
3 注意以下的数据
abcabcabcabc
abcabcabcabcabc
输出 12
abcabc
abc
输出 3
我们知道如果合并了s1和s2的话,那么求出来的最长的长度是24 和 6显然是不行的,因为我们忽略了一个地方就是求出的最长的前缀的长度是不能超过
s1和s2的长度的,所以求出最长前缀长度后应该进行讨论。
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define MAXN 100010 char s1[MAXN/2]; char s2[MAXN/2]; char pattern[MAXN]; int next[MAXN]; void getNext(){ int n = strlen(s1); int m = strlen(s2); next[0] = next[1] = 0; for(int i = 1 ; i < n+m ; i++){ int j = next[i]; while(j && pattern[i] != pattern[j]) j = next[j]; next[i+1] = pattern[i] == pattern[j] ? j+1 : 0; } if(!next[n+m]) printf("0\n"); else{ int tmp = next[m+n]; s1[tmp] = '\0'; if(n > m){/*如果第一串大于第二串*/ if(tmp > m)/*如果tmp>第二串长度直接输出第二串*/ printf("%s %d\n" , s2 , m); else printf("%s %d\n" , s1 , tmp); } else{/*如果第一串小于第二串*/ if(tmp > n)/*如果tmp>第一串的长度直接输出第一串*/ printf("%s %d\n" , s1 , n); else printf("%s %d\n" , s1 , tmp); } } } int main(){ while(scanf("%s" , s1) != EOF){ scanf("%s" , s2); memcpy(pattern , s1 , sizeof(s1)); strcat(pattern , s2); getNext(); } return 0; }
时间: 2024-08-31 14:52:48