Cod sursa(job #1391677)

Utilizator koroalinAlin Corodescu koroalin Data 18 martie 2015 09:04:41
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char p[NMAX],t[NMAX];
int n,m,pre[NMAX];
void constr_prefix();
vector <int> sol;
int main()
{
    int i,x=0;
    fin>>p; fin>>t;
    n=strlen(t); m=strlen(p);
    strcpy(p+1,p);
    strcpy(t+1,t);
    constr_prefix();
    for (i=1; i<=n; i++)
    {
        while (x && p[x+1]!=t[i]) x=pre[x];
        if (p[x+1]==t[i]) x++;
        if (x==m)
        {
            sol.push_back(i-m);
            x=pre[x];
        }
    }
    fout<<sol.size()<<'\n';
    for (i=0; i<sol.size() && i<1000; i++) fout<<sol[i]<<' ';
    fout<<'\n';
    fout.close();
    fin.close();
    return 0;
}
void constr_prefix()
{
    int k=0,x;
    pre[0]=0;
    for (x=2;x<=m; x++)
    {
        while (k && p[k+1]!=p[x]) k=pre[k];
        if (p[k+1]==p[x]) k++;
        pre[x]=k;
    }
}