題目分析 :
很久以前做的一個(gè)題目, 純粹的套模板了..... 到現(xiàn)在還是沒(méi)明白 KMP 到底怎么回事, 也可能是我沒(méi)花時(shí)間去仔細(xì)的看的原因.
今天上郵箱發(fā)現(xiàn)一個(gè)星期前一位網(wǎng)友問(wèn)我的1711代碼速度為什么那么快, 著到代碼一看, 原來(lái)是個(gè) 簡(jiǎn)單的KMP 裸題, 直接模板就行了,
速度的話這里有個(gè)小技巧, 知道的人就不要笑話我了.
其實(shí)關(guān)鍵就是 對(duì)輸入數(shù)據(jù)的 加速!!!!
一般對(duì)數(shù)據(jù)的輸入都是 %d 或 %f %lf 對(duì)吧? 其實(shí)計(jì)算機(jī)讀取的數(shù)據(jù)是字符形的, 它也需要調(diào)用其他的函數(shù)將這個(gè)串轉(zhuǎn)換成
數(shù)字, 所以你只要 用字符串讀入 數(shù)據(jù), 然后自己寫(xiě)個(gè)函數(shù) 把 這個(gè)字符串轉(zhuǎn)換成 數(shù)字久行了.
其實(shí)呢, 很多題目都可以只要來(lái)加速的, 除非它的數(shù)據(jù)量不大.
下面是我的代碼 :
#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) // 這個(gè)就是 加速的 關(guān)鍵了
{
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;
}