|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; #define MAXN 105 int lt[MAXN]; void getNext(char *str){ int len = strlen(str); for (int i=1; i<len; ++i) { int j=i; while (j>0) { j=lt[j]; if (str[j]==str[i]) { lt[i+1]=j+1; break; } } } } //生成kmp next的正确思路是不断迭代，一直迭代到不可能利用到之前next数组的程度（最坏情况迭代到和0比较）这个才是正确的方案 bool KMP(char *a,char *b){ //match a in b getNext(a); int lena = strlen(a),lenb = strlen(b); int cura = 0,curb = 0; while(curb < lenb){ while (cura < lena && curb < lenb){ if(b[curb] == a[cura]){ cura++,curb++; }else{ if(cura == 0) curb++; else cura = lt[cura]; } } if (curb >= lenb && cura != lena) break;//failed if(cura == lena){//success return true; } } return false; } char toProc[MAXN]; char mid[MAXN]; char last[MAXN]; int main(){ scanf(" %s",toProc); int len = strlen(toProc); for (int i = 1; i < len-1; i++) { mid[i-1] = toProc[i]; } memcpy(last, toProc, sizeof(toProc)); int lastlen = len; while (lastlen) { last[lastlen] = ' '; if (KMP(last,mid)) { printf("%sn",last); break; }else{ lastlen = lt[lastlen]; } } if (!lastlen) { printf("Just a legendn"); } return 0; } |
整个比赛都在搞这个题，还不知道哪里不对。
其实这个题如果用kmp做主要卡在这么几个地方：
首先要读懂题，aaaaaa的对应答案是aaaa，四个a，也就是说prefix是在不包括最后一个字符的范围内检索，suffix是在不包括第一个字符的区域检索，中间那个则是在既不包括第一个字符也不包括最后一个字符的范围内检索。
然后Next数组要机智地用好，就是说当前模版串失配之后，机智的方法是利用当前模版串的next数组，直接构造出下一个可能的模版串，而不是一次只删掉末尾的一个字符，再重新扫描这种暴力方法。
其实这个题上面两点我都没想到，更要命的是我的next数组构造方式就存在问题。
在这里重申一下正确的next数组构造方式，首先next[0] = 0,next[1] = 0(next[0]=-1也是可以的)，这个没什么好说的，然后要注意，在进行到中间的时候，首先检查next[当前位]对应的字符是不是和现在的字符相等，相等就在当前next的基础上＋1，赋值给下一位的next，如果没有匹配上这个时候不是简单的归零，而是要把当前的比较位置更新成当前比较位置对应的next值的对应位置，也就是一定要迭代回去。（我就是因为没有迭代，next数组整个就是错误的）