2015
07-16

# Spy

“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 105). You may assume that the input contains no more than 2 × 106 characters.
Input is terminated by EOF.

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 105). You may assume that the input contains no more than 2 × 106 characters.
Input is terminated by EOF.

abc
aab
aaabbbaaaabbbaa
abcababcd

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

#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 100005
int next[MAXN];
char s[MAXN],p[MAXN];
void getnext(int n,int st)
{
for(int i=st+1;i<n;i++)
{
int j=next[i];
while(j&&p[i]!=p[j])
{
j=next[j];
}
if(p[i]==p[j])
{
next[i+1]=j+1;
}
else
{
next[i+1]=0;
}
}
}
int ans;
int updata(int last,int now,int st)
{
// int len=strlen(p)   //因为加了这句,TLE调了我好久。
int len=st+1;
for(int i=last+1;i<=now;i++)
{
p[len++]=s[i];
}
p[len]='\0';
getnext(len,st);
return len;
}
int kmp(int m)
{
getnext(m,0);
int j=0;
int last;
for(int i=0;s[i];i++)
{
while(j&&s[i]!=p[j])
j=next[j];
if(j==0&&s[i]!=p[j])
{
m=updata(last,i,m-1);
last=i;
}
if(s[i]==p[j])
j++;
if(j==m)
{
last=i;
}
}
for(int i=last+1;s[i];i++)
m++;
ans=m;
return -1;
}
int main()
{
int cas=1;
while(scanf("%s",&s)!=EOF)
{
memset(next,0,sizeof(next));
p[0]=s[0];
p[1]='\0';
ans=1;
kmp(1);
printf("Case %d: %d\n",cas++,ans);
}
}