首页 > ACM题库 > HDU-杭电 > HDU 4468-Spy-KMP-[解题报告]HOJ
2015
07-16

HDU 4468-Spy-KMP-[解题报告]HOJ

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
abcadabcabcad
aaabbbaaaabbbaa
abcababcd

样例输出:

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

题意,给定一个字符串S,用另一个字符串T,  以  T的前缀1 + T的前缀2 + …… + T   的形式来得到S,求T的最小长度。

集训队比赛的时候,我们想到的是枚举后缀,然后匹配,因为这样保证了后缀一定满足,但这样的话,长度必须一个个向上加,而且每次都要遍历一遍字符串,果断TLE了。

看了题解才知道,枚举前缀加上贪心的思想可以更快,而且做倒O(n)的复杂度。

首先我们把模式串p定为s[0],然后进行匹配,当匹配过程中出现失配(设失配的字符为Z),并且一直失配到头指针且和头字符不相等的时候,我们就把 文本串中从上一次完美匹配的位置到当前位置的所有字符 全部加入到p后。(为什么可以这样,因为Z是p中一个未出现过的字符,所以Z不可能作为一个前缀字符,并且只能作为最后一个字符,而当它作为最后一个字符的时候,前面的那些非完美匹配的字符就只能跟在它前面了。)

至于要满足后缀,只需要把文本串中从 最后一次完美匹配的位置到文本末尾 所有的字符加入p后就可以了。

匹配过程复杂度为O(n),next函数由于可以边加边算,所以复杂度上限也就是 O(n),甚至文本串的长度都可以不用遍历一遍求出,所以总的复杂度不会超过O(2n)

贴代码。

#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);
    }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/t1019256391/article/details/9405897