Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int n , k , poz, m , L[1003] , P[1003] , T[1003] ;
- int main()
- {
- //ifstream f("Kmp.in") ;
- //ofstream g("Kmp.out") ;
- cin>>n ;
- for(int i=1;i<=n;i++)
- cin>>T[i] ;
- cin>>m ;
- for(int i=1;i<=m;i++)
- cin>>P[i] ;
- k=0 ;
- L[1]=0 ;
- int p,t ;
- for(p=2;p<=m;p++)
- {
- while(k>0 && P[k+1]!=P[p])
- k=L[k] ;
- if(P[k+1]==P[p])
- k++ ;
- L[p]= k ;
- }
- int ok = 0 ;
- k=0 ;
- for(t=1;t<=n;t++)
- {
- while(k>0 && P[k+1]!=T[t])
- k=L[k] ;
- if(P[k+1]==T[t])
- k++ ;
- if(k==m)
- {
- poz = t-k + 1 ;
- ok=1 ;
- k=L[k] ;
- break ;
- }
- }
- if(ok==0)
- cout<<"NU" ;
- else
- cout<<poz ;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement