Cod sursa(job #2445021)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 2 august 2019 11:28:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int DIM = 2e6;

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

int pi[DIM + 5];
int ans;
vector <int> kmp;

void Pi()
{
    int j = 0;

    for(int i = 2; i <= N; i++) {

        while(a[i] != a[j + 1] && j != 0)
            j = pi[j];

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

        pi[i] = j;

    }
}

void Kmp()
{
    int j = 0;

    for(int i = 1; i <= M; i++) {

        while(b[i] != a[j + 1] && j != 0)
            j = pi[j];

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

        if(j == N) {

            ans++;
            if(kmp.size() <= 1000)
                kmp.push_back(i - N);

            j = pi[j];
        }

    }
}

int main()
{
    fin >> (a + 1); N = strlen(a + 1);
    fin >> (b + 1); M = strlen(b + 1);

    Pi();

    Kmp();

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

    return 0;
}