Cod sursa(job #1725858)

Utilizator Emy1337Micu Emerson Emy1337 Data 6 iulie 2016 16:42:41
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int MAXN = 2e6+5;
int v[MAXN];
string text, sablon;
vector <int> rez;

void prefix()
{
    int i = 1, j = 0;
    while(i < sablon.size())
    {
        if(sablon[i] == sablon[j])
            v[i++] = ++j;
        else
        {
            if(j!=0)
                j = v[i-1];
            else
                i++;
        }
    }
}

void kmp()
{
    int i = 0, j = 0;
    while(i < text.size())
    {
        if(text[i] == sablon[j])
            i++, j++;
        else
        {
            if(j!=0)
                j = v[j-1];
            else
                i++;
        }

        if(j == sablon.size())
            rez.push_back(i-j);
    }
}

int main()
{
    fin>> sablon >> text;

    prefix();
    kmp();

    fout<<rez.size() << endl;
    for(auto it: rez)
        fout<<it << " ";
}