HDU 1711（KMP）字符串匹配

链接 HDU 1711 Number Sequence

KMP 算法

我以自己理解写的，写的不对，不明白的地方海王子出来，一起共同学习；

字符串匹配就是KMP，一般思想，用一个for循环找开头如果开头一样进入第二个for循环；这样统计直观容易理解。但是时间复杂度比较长。所以就有KMP 这个算法了

KMP 大体思想因为在上一个方法之中，有的字符重复比较了，使得找到目标字符窜效率比较低，

比如：目标串为： ① a b a b c

在 ② a b a a b a b c d a b c d b c 这个字符窜中找到上述目标串；

如用 i，j 来表示①，②两个字符串的下标，假设下标从一开始；

i=1,j=1 a=a;

i=2,j=2 b=b;

i=3,j=3 a=a;

i=4;j=4 b!=a; 此时如果只将①字符串右移动一位，虽然可以；但是，假如你移动两位看看怎么样？

a b a b c

a b a a b a b c d a b c d b c

是不是觉得移动2格对得非常整齐？

那么为什么移动两个？

第3个a与第一个a正好重复！所以我们知道重复单元就知道移动多少。需要一个数组记录当两个字符不相等，i 应该指向哪个！记录重复单元的值，叫做部分匹配值！不懂可以百度部分匹配值！以上就是KMP 核心思想

下面贴一个代码！！两种写法！//屏蔽是另一种写法

[cpp] view
plain copy

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int N[1000005],M[10005],a[10005],n,m;
void set_a()
{
int i,j;
a[1]=0;
j=1;
for(i=2; i<=m; i++)
{
if(M[j]==M[i])
{
a[i]=j;
j++;
}
else if(M[j]!=M[i]&&M[i]==M[1])
{
a[i]=1;
j=2;
}
else
{
a[i]=0;
j=1;
}
}
// for(i=1; i<=m; i++)
// printf("%d ",a[i]);
// printf("\n");
}
int kmp()
{
int i=1,j=1,k;
set_a();
while(i<=n)
{
if(j==1&&N[i]!=M[j]) i++;
if(N[i]==M[j])
{
i++;
j++;
}
else j=a[j-1]+1;
if(j==m+1) return i-m;
}
return -1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
//int b; scanf("%d",&b);
int i;
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
for(i=1; i<=n; i++)
scanf("%d",&N[i]);
for(i=1; i<=m; i++)
scanf("%d",&M[i]);
printf("%d\n",kmp());
}
return 0;
}
///**********************KMP****************************/
//
//#include<stdio.h>
//#include<string.h>
//using namespace std;
//int lena,lenb;
//int a[1000005],b[10005];
//int next[200000];
//void set_naxt()//子串的next数组
//{
// int i=0,j=-1;
// next[0]=-1;
// while(i<lenb)
// {
// if(j==-1||b[i]==b[j])
// {
// i++;
// j++;
// next[i]=j;
// }
// else
// j=next[j];
// }
// // printf(">>%d\n",next[lenb-1]);
// for(i=1; i<=lenb; i++)
// printf("%d ",next[i]);
// printf("\n");
//}
//
//int kmp()
//{
// int i=0,j=0;
// set_naxt();
// while(i<lena)
// {
// if(j==-1||a[i]==b[j])
// {
// i++;
// j++;
// }
// else
// j=next[j];
// if(j==lenb)
// return i-j+1;
// }
// return -1;
//}
//int main()
//{
// int i,t;
// scanf("%d",&t);
// while(t--)
// {
// memset(next,0,sizeof(next));
// scanf("%d%d",&lena,&lenb);
// for(i=0; i<lena; i++)
// scanf("%d",&a[i]);
// for(i=0; i<lenb; i++)
// scanf("%d",&b[i]);
// printf("%d\n",kmp());
// }
//}

巴特西

HDU 1711（KMP）字符串匹配

最新文章

热门文章