Cod sursa(job #1369076)

Utilizator StefanMudragMudrag Stefan StefanMudrag Data 2 martie 2015 21:34:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<vector>
#define NMAX 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[NMAX],p[NMAX];
int urm[NMAX],n,m;
void prefix(char *p)
{
    int k=0,i;
    urm[1]=0;
    for(i=2;i<=m;i++)
    {
        while(k&&p[k+1]!=p[i])k=urm[k];
        if(p[k+1]==p[i])
            k++;
        urm[i]=k;
    }

}


int main()
{
   fin.getline(p+1,NMAX);
   fin.getline(s+1,NMAX);
   m=strlen(p+1);
   n=strlen(s+1);
   int nr=0;
  prefix(p);int k=0;
  vector<int>sol;
  for(int i=1;i<=n;i++)
  {
      while(k&&p[k+1]!=s[i])k=urm[k];
       if(p[k+1]==s[i])
          k++;
       if(k==m)
       {    nr++;
           if(nr<=1000)sol.push_back(i-m);
           k=urm[k];
       }
  }
  fout<<nr<<'\n';
  for(int i=0;i<sol.size()&&i<=1000;++i)
     fout<<sol[i]<<" ";
   fin.close();
   fout.close();
   return 0;
}