kmphdu1711

     kmp让自己意识到自己到底是有多么的水.纠结了好几天,终于对kmp算是有了一个比较浅显的认识.
    打开任何一篇关于kmp的文章后,你都会接触一个叫做next数组的东西,其实,不管七大姨八大姑,kmp的关键就是求一个字符串的前缀和后缀的最大公共长度,不知我说的准确吧,那么我们就应该找出与此有关的东西来.我们以"ababaca"为例尝试着计算next数组.
    首先我们先了解一下前缀后缀的概念.
    前缀:除最后一个字符的所有字符组合;后缀:除第一个字符的的所有字符组合.
"ababaca" 前缀为
    
    "a,ab,aba,abab,ababa,ababac"
    后缀为
    "a,ca,aca,baca,abaca,babaca"
不要被迷惑,这只是指向第6个(从0开始)字母a的前缀,那么我们可以数数只有a自己相同,所以next[6]=1;我们现在将指向"ababaca"中第四个(从0开始)a,它的前缀为:"a,ab,aba,abab",后缀为"a,ba,aba,baba",前后对比一下,"aba"就是,也就是3了.依次类推,下面我是摘自 
stackoverflow的解答,我们推得这个字符串的next[]为
# | String | P(#) | Longest matching prefix-suffix
0 | "a" | 0 | ""
1 | "ab" | 0 | ""
2 | "aba" | 1 | "a" -- a b a
3 | "abab" | 2 | "ab" -- ab ab
4 | "ababa" | 3 | "aba" -- ab a ba
5 | "ababac"| 0 | ""
6 |"ababaca"| 1 | "a" -- a babac a

    我们将next数组计算出来以后,其余的就好说了,在匹配的时候,总的思想还是kmp数组的算法思想.

即便说到这,当时我还是死活看不懂,用手找个例子运行一下.

--------------------------------------------------------------------------------------------------------------------------------

hdu 1711只是适合这个思想,题目稍微简单,哎,做个字符串的题目真是难受,就是简简单单的字符串输入输出就搞得头大,看来得花费一定的时间将它处理好.

总共提交了4次,通过这次我有点理解为什么zoj上的那道题不对了,不要用大数组作为函数的参数,虽然我现在讲不出理由,但直观的想想,即使传址来回跑多累,

#include
#include
using namespace std;
int text[1000010];
int pattern[10010];
int n,m;
int next[10010];
void getnext()
{
int k=0;
next[0]=0;
int i;
for(i=1;i {
while(k>0 && pattern[k] != pattern[i])
{
k=next[k-1];//k就是前缀后缀最长的数目
}
if(pattern[i]==pattern[k])
{
k++;
}
next[i]=k;
}
}
int kmp()
{
int i,q;
getnext();
q=0;
for(i=0;i {
while(q>0 && pattern[q] != text[i])
q=next[q-1];
if(pattern[q] == text[i])
{
q++;
}
if(q == m)
{
return i-m+2;
break;
}
}
return -1;
}
int main()
{
// freopen("in.txt","r",stdin);
int i;
int kcase;

scanf("%d",&kcase);
while(kcase--)
{
scanf("%d%d",&n,&m);
for(i=0;i scanf("%d",&text[i]);
for(i=0;i scanf("%d",&pattern[i]);
if(n {
printf("-1\n");
continue;
}
getnext();
printf("%d\n",kmp());
}
}

kmp hdu-1711,布布扣,bubuko.com