Advertisement
Guest User

Untitled

a guest
Apr 1st, 2015
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.88 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int n , k , poz, m , L[1003] , P[1003] , T[1003] ;
  6.  
  7. int main()
  8. {
  9. //ifstream f("Kmp.in") ;
  10. //ofstream g("Kmp.out") ;
  11.  
  12. cin>>n ;
  13. for(int i=1;i<=n;i++)
  14. cin>>T[i] ;
  15. cin>>m ;
  16. for(int i=1;i<=m;i++)
  17. cin>>P[i] ;
  18.  
  19. k=0 ;
  20. L[1]=0 ;
  21.  
  22. int p,t ;
  23.  
  24. for(p=2;p<=m;p++)
  25. {
  26. while(k>0 && P[k+1]!=P[p])
  27. k=L[k] ;
  28.  
  29. if(P[k+1]==P[p])
  30. k++ ;
  31. L[p]= k ;
  32.  
  33. }
  34. int ok = 0 ;
  35. k=0 ;
  36. for(t=1;t<=n;t++)
  37. {
  38. while(k>0 && P[k+1]!=T[t])
  39. k=L[k] ;
  40.  
  41. if(P[k+1]==T[t])
  42. k++ ;
  43. if(k==m)
  44. {
  45. poz = t-k + 1 ;
  46. ok=1 ;
  47. k=L[k] ;
  48. break ;
  49. }
  50. }
  51.  
  52. if(ok==0)
  53. cout<<"NU" ;
  54. else
  55. cout<<poz ;
  56.  
  57. return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement