Cod sursa(job #1144612)

Utilizator Claudiu95Vartolomei Alexandru Claudiu Claudiu95 Data 17 martie 2014 12:56:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 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=-1,x;
    urm[0]=0;
    for( x=1;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);
    m=strlen(P);
    x=-1;
    urmator(P);

    for(int i=0;i<n;++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-1){

            ++nr;
            sol[nr]=i-m+1;
            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;


}