题目分析 :
很久以前做的一个题目, 纯粹的套模板了..... 到现在还是没明白 KMP 到底怎么回事, 也可能是我没花时间去仔细的看的原因.
今天上邮箱发现一个星期前一位网友问我的1711代码速度为什么那么快, 着到代码一看, 原来是个 简单的KMP 裸题, 直接模板就行了,
速度的话这里有个小技巧, 知道的人就不要笑话我了.
其实关键就是 对输入数据的 加速!!!!
一般对数据的输入都是 %d 或 %f %lf 对吧? 其实计算机读取的数据是字符形的, 它也需要调用其他的函数将这个串转换成
数字, 所以你只要 用字符串读入 数据, 然后自己写个函数 把 这个字符串转换成 数字久行了.
其实呢, 很多题目都可以只要来加速的, 除非它的数据量不大.
下面是我的代码 :
#include <iostream>
using namespace std;
const int MAXN=1000000;
const int MAXM=10000;
int nn[MAXN+1],mm[MAXM+1];
int Fail[MAXM+1];
void GetFail(int num[],int m){
Fail[0]=-1;
for(int i=1,j=-1;i<m;i++){
while(j>=0&&num[j+1]!=num[i]){
j=Fail[j];
}
if(num[j+1]==num[i])j ++;
Fail[i]=j;
}
}
int KMP(int numA[],int numB[],int n,int m){
GetFail ( numB,m );
for (int i=0,j=0;i<n;i++){
while(j&&numB[j]!=numA[i]){
j=Fail[j-1]+1;
}
if(numB[j]==numA[i]) j++;
if(j == m) return i-m+2;
}
return -1;
}
inline bool scan_d(int &num) // 这个就是 加速的 关键了
{
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-'){ IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9'){
num*=10,num+=in-'0';
}
if(IsN) num=-num;
return true;
}
int main ()
{
int N,M,T;
while ( scan_d(T) )
{
while ( T -- )
{
scan_d(N),scan_d(M);
for ( int i = 0; i != N; ++ i )
scan_d ( nn[i] );
for ( int j = 0; j != M; ++ j )
scan_d ( mm[j] );
printf ( "%d\n",KMP ( nn,mm,N,M ) );
}
}
return 0;
}