Cod sursa(job #2023103)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 18 septembrie 2017 11:15:46
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>
#include <string>
#define Nmax 2000005
using namespace std;

string A,B;

int pi[Nmax],w;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

vector <int> rez;

int main()
{
    int i,cnt=0;
    f>>A>>B;
    for(i=1; i<A.size(); i++)
    {
        while(w!=0 && A[i]!=A[w]) w=pi[w-1];

        if(A[i]==A[w])
            w++;

        pi[i]=w;
    }
    w=0;
    for(i=1; i<B.size(); i++)
    {
        while(w!=0 && B[i]!=A[w]) w=pi[w-1];

        if(B[i]==A[w])
            w++;

        if(w==A.size())
        {
            cnt++;
            rez.push_back(i-A.size()+1);
        }
    }
    g<<cnt<<'\n';
    for(auto it:rez)
    g<<it<<" ";
    return 0;
}