Cod sursa(job #2381966)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 17 martie 2019 14:58:57
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

#define NM 5000002

using namespace std;

string a, b;

int n;

string s;

int kmp[NM];

vector <int> ans;

int main()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    fin >> a >> b;
    s += ' ';
    s += a;
    s += '$';
    s += b;
    n = s.size() - 1;
    kmp[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        kmp[i] = kmp[i - 1];
        while(kmp[i] > 0 && s[i] != s[kmp[i] + 1])
            kmp[i] = kmp[kmp[i]];
        if(s[i] == s[kmp[i] + 1])
            kmp[i]++;
        if(kmp[i] == a.size())
            ans.push_back(i - 2 * kmp[i] - 1);

    }
    fout << ans.size() << "\n";
    for(int i = 0; i < min(ans.size(), 1000u); i++)
        fout << i << " ";
    fout << "\n";
    return 0;
}