Cod sursa(job #761940)

Utilizator stefanzzzStefan Popa stefanzzz Data 27 iunie 2012 21:33:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 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){
            x=fct[x-1];
            v[0]++;
            if(v[0]<=1000)
                v[v[0]]=i-lgp+1;}}
    g<<v[0]<<'\n';
    if(v[0]>1000)
        v[0]=1000;
    for(i=1;i<=v[0];i++)
        g<<v[i]<<' ';
    f.close();
    g.close();
    return 0;
}