Cod sursa(job #1725866)

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

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

const int MAXN = 2e6+5;
int v[MAXN], nr;
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()){
           nr++;
           if(sablon.size() < 1000) rez.push_back(i-j);
        }
    }
}

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

    prefix();
    kmp();

    fout<<nr << endl;

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