Cod sursa(job #1552501)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 18 decembrie 2015 10:57:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2000000 + 10;

int ans , N , M;
int phi[Nmax];

vector < int > v;

string a , b;

void makePhi()
{
    int k;

    phi[1] = 0;
    for (int i = 2; i <= N; ++i)
    {
        k = phi[i-1];
        while (k && a[i] != a[k+1])
            k = phi[k];

        phi[i] = (a[i] == a[k+1]) ? k + 1 : 0;
    }
}

void makeKmp()
{
    int k = 0;
    for (int i = 1; i <= M; ++i)
    {
        while (k && b[i] != a[k+1])
            k = phi[k];

        if (b[i] == a[k+1]) k++;
        if (k == N)
        {
            ans++;
            if (ans < 1000) v.push_back(i-N);
        }
    }
}

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    fin >> a; a = ' ' + a + '$';
    fin >> b; b = ' ' + b;
    N = a.size() - 2; M = b.size() - 1;

    //cerr << a << ' ' << b;

    makePhi(); makeKmp();

    fout << ans << '\n';
    for (auto &it : v)
        fout << it << ' ';
    fout << '\n';

    return 0;
}