hdu4468 Spy kmp

“Be subtle! Be subtle! And use your spies for every kind of business. ”
— Sun Tzu
“A spy with insufficient ability really sucks”
— An anonymous general who lost the war
You, a general, following Sun Tzu’s instruction, make heavy use of spies and agents to gain information secretly in order to win the war (and return home to get married, what a flag you set up). However, the so-called “secret message” brought back by your spy, is in fact encrypted, forcing yourself into making deep study of message encryption employed by your enemy.
Finally you found how your enemy encrypts message. The original message, namely s, consists of lowercase Latin alphabets. Then the following steps would be taken:
* Step 1: Let r = s
* Step 2: Remove r’s suffix (may be empty) whose length is less than length of s and append s to r. More precisely, firstly donate r[1...n], s[1...m], then an integer i is chosen, satisfying i ≤ n, n - i < m, and we make our new r = r[1...i] + s[1...m]. This step might be taken for several times or not be taken at all.
What your spy brought back is the encrypted message r, you should solve for the minimal possible length of s (which is enough for your tactical actions).

There are several test cases.
For each test case there is a single line containing only one string r (The length of r does not exceed 10 ⁵). You may assume that the input contains no more than 2 × 10 ⁶ characters.
Input is terminated by EOF.

For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) and Y is the desired answer.

  
abc
aab
abcadabcabcad
aaabbbaaaabbbaa
abcababcd

  
Case 1: 3
Case 2: 2
Case 3: 5
Case 4: 6
Case 5: 4

2012 Asia Chengdu Regional Contest

liuyiding

这题，我们可以很容易看出也是kmp,那么怎么做呢?我们就是要去模式串满足其前缀可以拼成原串，且是原串的后缀，我们可以先不管后缀，我们先找前缀满足，我们先为原串的第一个字符，然后，我们，与原串匹配，如果，发现不能匹配，就把上一次完全匹配的地方到这里的全加入模式串，一直到最后，不就得出答案了么？如果到了最后，不是反缀，就可以，再加入新的，否则直接输出就可以了！

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MAXN 100000
char str[MAXN],pass[MAXN];
int next[MAXN],passnum,strnum,lastpass;
void getnext()
{int i,j;next[0]=next[1]=0;for(i=lastpass,j=0;i<passnum;i++){j=next[i];while(j&&pass[i]!=pass[j]){j=next[j];}next[i+1]=pass[i]==pass[j]?j+1:0;}}
int fkmp()
{int i,j,last,k;last=1;for(i=1,j=0;i<strnum;i++)//??{while(j&&str[i]!=pass[j]){j=next[j];}if(str[i]==pass[j]){j++;}if(j==0){lastpass=passnum;for(k=last;k<=i;k++){pass[passnum++]=str[k];}last=i+1;pass[passnum]='\0';getnext();//printf("%s %d %d %d\n",pass,i,j,passnum);}if(j==passnum){last=i+1;j=0;//完全}}if(last==strnum)return passnum;elsereturn strnum-last+passnum;
}
int main()
{int tcase=1;while(scanf("%s",str)!=EOF){strnum=strlen(str);lastpass=1;passnum=1;pass[0]=str[0];pass[1]='\0';printf("Case %d: %d\n",tcase++,fkmp());}return 0;
}