KMP模板（HDU1711）-白红宇

KMP模板（HDU1711）

阅读量：4708 次

发布时间：2019-06-10

本文共 1186 字，大约阅读时间需要 3 分钟。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define MAXN 1010100#define LL long long#define ll __int64#define INF 0x7fffffff#define cs(s) freopen(s,"r",stdin)#define mem(x) memset(x,0,sizeof(x))#define PI acos(-1)#define eps 1e-10using namespace std;int gcd(int a,int b){ return b?gcd(b,a%b):a;}int lcm(int a,int b){ return a/gcd(a,b)*b;}LL powmod(LL a,LL b,LL MOD){ LL ans=1;while(b){ if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}//headint t,m,n;int pattern[1101001],text[1001001];vector 
             
               find_substring(int pattern[],int text[]){ vector
              
                nex (n+1,0); for(int i=1;i
               
                0) { j=nex[j]; if(pattern[j]==pattern[i]){ nex[i+1]=j+1;break;} } } vector
                
                 pos; for(int i=0,j=0;i
                 
                  0){ j=nex[j]; if(text[i]==pattern[j]){ j++; break; } } } if(j==n)pos.push_back(i-n+1); } return pos;}int main(){ ios::sync_with_stdio(false); for(cin>>t;t;t--){ cin>>m>>n; for(int i=0;i
                  
                   >text[i]; for(int i=0;i
                   
                    >pattern[i]; vector
                    
                     ans=find_substring(pattern,text); if(!ans.size())cout<<-1<<'\n'; else cout<
                     
                      <<'\n'; } return 0;}