Cod sursa(job #1144671)

Utilizator Claudiu95Vartolomei Alexandru Claudiu Claudiu95 Data 17 martie 2014 13:49:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include<fstream>
#include<algorithm>
#include<string.h>
#define maxx 2000005

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");
char P[maxx],T[maxx];
 int urm[maxx],m,x,n,sol[1005],nr;
void urmator(char *p){
    int k=0,x;
    urm[1]=0;
    for( x=2;x<=m;++x){
        while(k>0 && p[k+1]!=p[x])
            k=urm[k];
        if(p[k+1]==p[x])
            ++k;
        urm[x]=k;
    }
}


int main(){
f.getline(P,maxx);
    f.getline(T,maxx);

    n=strlen(T);

    for(int i=n;i>0;--i)
        T[i]=T[i-1];
    T[0]=' ';
    m=strlen(P);
   for(int i=m;i>0;--i)
        P[i]=P[i-1];
    P[0]=' ';
    x=0;
    urmator(P);

    for(int i=1;i<=n && nr<1002;++i){
        while(x>0 && P[x+1]!=T[i])
            x=urm[x];
        if(P[x+1]==T[i])
            ++x;
        //else
          //  x=-1;
        if(x==m){

            ++nr;
            sol[nr]=i-m;
            x=urm[x];
            }
    }
  /*  for(int i=0;i<m;++i)
        g<<urm[i]<<" ";
    */
    g<<nr<<"\n";
    if(nr>1000)
        for(int i=1;i<=1000;++i)
            g<<sol[i]<<" ";
    else
    for(int i=1;i<=nr;++i)
    g<<sol[i]<<" ";
return 0;


}