Cod sursa(job #1524149)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 13 noiembrie 2015 16:33:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstring>
#define size 2000000

using namespace std;

std::stringstream rez;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int next[size], n, m, total;
char T[size], P[size];

void TheNextOne(char *P)
{
    int k=-1, x;
    next[0]=0;
    for (x=1; x<n; ++x)
    {
        while (k>0 && P[k+1]!=P[x]) k=next[k];
        if (P[k+1]==P[x]) ++k;
        next[x]=k;
    }
}

int main()
{
    int x=-1;
    fin.getline(P,size); n=strlen(P);
    fin.getline(T,size); m=strlen(T);
    TheNextOne(P);
    for (int i=0; i<m; ++i)
    {
        while (x>0&&P[x+1]!=T[i]) x=next[x];
        if (P[x+1]==T[i]) ++x; // s-au potrivit
        if (x==n-1)
        {
            ++total;
            rez<<i-n+1<<' ';
            x=next[x];
        }
    }
    fout<<total<<'\n'<<rez.str();
    return 0;
}