Cod sursa(job #2415501)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 26 aprilie 2019 09:30:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int NMAX = 2000000;

int N, M;
char a[NMAX + 5], b[NMAX + 5];

int pi[NMAX + 5];

int ans;
vector <int> sol;

void Pi()
{
    int j = 0;

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

        if(a[j + 1] == a[i])
            j++;

        pi[i] = j;
    }
}

void Kmp()
{
    int j = 0;

    for(int i = 1; i <= M; i++)
    {
        while(j != 0 && a[j + 1] != b[i])
            j = pi[j];

        if(a[j + 1] == b[i])
            j++;

        if(j == N)
        {
            ans++;

            if(ans <= 1000)
                sol.push_back(i - N);

            j = pi[j];
        }
    }

    fout << ans << '\n';
    for(auto it : sol)
        fout << it << ' ';
}

int main()
{
    fin >> (a + 1) >> (b + 1);

    N = strlen(a + 1);
    M = strlen(b + 1);

    Pi();

    Kmp();

    return 0;
}