Cod sursa(job #2880180)

Utilizator pctirziuTirziu Petre pctirziu Data 29 martie 2022 14:59:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int cnt;
string s, patt;
int lcs[2000005];
vector <int> ans;
void precalc()
{
    int i = 1, j = 0;
    lcs[0] = 0;
    while(i < patt.size()){
        if(patt[i] == patt[j]){
            j++;
            lcs[i] = j;
            i++;
        }
        else{
            if(j)
                j = lcs[j - 1];
            else
                lcs[i] = 0, i++;

        }
    }
}
void kmp()
{
    int i = 0, j = 0;
    while(i < s.size()){
        if(patt[j] == s[i])
            ++i, ++j;
        if(j == patt.size()){
            ans.push_back(i - j);
            j = lcs[j - 1];
        }
        else if(i < s.size() and patt[j] != s[i]){
            if(j)
                j = lcs[j - 1];
            else
                i++;
        }
    }
}
int main()
{
    int n, i, j;
    cin >> patt >> s;
    precalc();
    kmp();
    cout << ans.size() << "\n";
    int x = ans.size();
    for(i = 0; i < min(1000, x); i++)
        cout << ans[i] << " ";
    //for(i = 0; i < patt.size(); i++)
        //cout << precalc[i] << " ";
    return 0;
}