Cod sursa(job #761916)

Utilizator stefanzzzStefan Popa stefanzzz Data 27 iunie 2012 20:47:04
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]=-1;
    for(i=1;i<lgp;i++){
        x=fct[i-1];
        while(x>=0&&p[x+1]!=p[i])
            x=fct[x];
        if(p[x+1]==p[i])
            x++;
        fct[i]=x;}
    x=-1;
    for(i=0;i<lgt;i++){
        while(x>=0&&t[i]!=p[x+1])
            x=fct[x];
        if(t[i]==p[x+1])
            x++;
        if(x==lgp-1){
            v[0]++;
            v[v[0]]=i-lgp+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;
}