Cod sursa(job #761937)

Utilizator stefanzzzStefan Popa stefanzzz Data 27 iunie 2012 21:08:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char p[2000010],t[2000010];
long fct[2000005],lgp,lgt,x,v[1005];

int main()
{
    long i;
    f.getline(p,2000005,'\n');
    f.getline(t,2000005,'\n');
    lgp=strlen(p);
    lgt=strlen(t);
    fct[0]=0;
    for(i=1;i<lgp;i++){
        x=fct[i-1];
        while(x>0&&p[x]!=p[i])
            x=fct[x-1];
        if(p[x]==p[i])
            x++;
        fct[i]=x;}
    x=0;
    for(i=0;i<lgt;i++){
        while(x>0&&t[i]!=p[x])
            x=fct[x-1];
        if(t[i]==p[x])
            x++;
        if(x==lgp){
            v[++v[0]]=i-lgp+1;
            x=fct[x-1];
            if(v[0]==1000)
                break;}}
    g<<v[0]<<'\n';
    for(i=1;i<=v[0];i++)
        g<<v[i]<<' ';
    f.close();
    g.close();
    return 0;
}