RQNOJ382[自然的谜语]

KMP练习,第一次写KMP。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-6-12


DESCRIPTION:


RQNOJ382


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <string>


using std::string;


#include <vector>


using std::vector;


 


class Application


{


      string s1,s2;


      public:


      Application()


      {


                   std::ios::sync_with_stdio(false);


                   cin>>s1>>s2;


      }


      int run()


      {


          vector<int> shift;


          int i,j;


          vector<int> pi(s1.length());


          j=pi[0]=-1;


          for (i=1;i<s1.length();i++)


          {


              while (j>=0&&s1[j+1]!=s1[i]) j=pi[j];


              if (s1[j+1]==s1[i]) j++;


              pi[i]=j;


          }


          j=-1;


          for (i=0;i<s2.length();i++)


          {


              while (j>=0&&s1[j+1]!=s2[i]) j=pi[j];


              if (s1[j+1]==s2[i]) j++;


              if (j==s1.length()-1)


                 j=pi[j],shift.push_back(1+(i-s1.length()+1));


          }


          if (shift.size())


             for (cout<<shift.size()<<endl,i=0;i<shift.size();i++)


                 cout<<shift[i]<<endl;


          else cout<<“There must be something wrong.”<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}