Cod sursa(job #2085514)

Utilizator MoleRatFuia Mihai MoleRat Data 10 decembrie 2017 12:15:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <string.h>
using namespace std;
char T[2000001],P[2000001];
char TT[4000002];
int FF[4000002];
int r,i,rez,n;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int main()
{
    fi>>P;
    n=strlen(P);
    fi>>T;
    TT[0]='\0';
    strcat(TT,P);
    strcat(TT,"*");
    strcat(TT,T);
    FF[0]=0;
    for (i=1;TT[i]!='\0';i++)
    {
        r=FF[i-1];
        while (r>0)
        {
            if (TT[i]==TT[r])
                break;
            r=FF[r-1];
        }
        if (TT[i]==TT[r])
            FF[i]=r+1;
        else
            FF[i]=0;
    }
    rez=0;
    for (i=0;TT[i]!='\0';i++)
        if (FF[i]==n)
            rez++;
    fo<<rez<<"\n";
    int nrsol=0;
    for (i=0;TT[i]!='\0';i++)
        if (FF[i]==n)
        {
            fo<<i-n-n<<" ";
            nrsol++;
            if (nrsol==1000)
                break;
        }
    fi.close();
    fo.close();
    return 0;
}