[HDU 2594]Simpsons’ Hidden Talents[kmp求公共前后缀]
题意:
求两个串s1, s2中s1的前缀与s2的后缀的最长公共部分.
思路:
next数组应用.
注意先判断主串是否结束, 再判断模式串是否结束. 1WA><
#include <cstring>#include <cstdio>#include <algorithm>const int MAXN = 50005;int next[MAXN],ans;char s1[MAXN];char s2[MAXN];//15MS492Kvoid prekmp(){ next[0] = -1; int j = -1; for(int i=1;s1[i];i++) { while(j!=-1 && s1[j+1]!=s1[i]) j = next[j]; if(s1[j+1]==s1[i]) j++; next[i] = j; }}void kmp(){ int j=-1; ans = 0; for(int i=0;s2[i];i++) { while(j!=-1 && s1[j+1]!=s2[i]) j = next[j]; if(s1[j+1]==s2[i]) j++; if(!s2[i+1]) { ans = j+1; s1[ans] = '\0'; } if(!s1[j+1]) j = next[j]; }}int main(){ while(~scanf("%s",s1)) { scanf("%s",s2); prekmp(); kmp(); if(ans) printf("%s %d\n",s1,ans); else printf("0\n"); }}