Cod sursa(job #1687112)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 12 aprilie 2016 17:53:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e6 + 10;

int asize , bsize , nr;
vector < int > v;

char a[nmax] , b[nmax];
int phi[nmax];

void bagaphi()
{
    int k = 0;

    phi[1] = k;
    for (int i = 2; i <= asize; ++i)
    {
        while (k && a[k+1] != a[i]) k = phi[k];
        if (a[k+1] == a[i]) k++;
        phi[i] = k;
    }
}

void bagakmp()
{
    int k = 0;
    for (int i = 1; i <= bsize; ++i)
    {
        while (k && a[k+1] != b[i]) k = phi[k];
        if (a[k+1] == b[i]) k++;
        if (k == asize)
        {
            nr++;
            if (nr <= 1000) v.push_back(i-asize);
        }
    }
}

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

    fin >> (a + 1) >> (b + 1);
    asize = strlen(a+1);
    bsize = strlen(b+1);

    bagaphi();
    bagakmp();

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

    return 0;
}