題目分析 :
很久以前做的一個題目, 純粹的套模板了..... 到現在還是沒明白 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;
}