Cod sursa(job #2817379)

Utilizator ElizaTElla Rose ElizaT Data 13 decembrie 2021 16:28:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e6;
int pi[NMAX + 5],ans[1005];

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    int n,m,cnt = 0,k;
    string s1,s2;
    fin >> s1 >> s2;
    n = s1.size();
    m = s2.size();
    k = -1;
    pi[0] = -1;
    for (int i = 1;i < n;i++) {
        while (k >= 0 && s1[k + 1] != s1[i])
            k = pi[k];
        if (s1[k + 1] == s1[i])
            k++;
        pi[i] = k;
    }
    k = -1;
    for (int i = 0;i < m;i++) {
        while (k >= 0 && s1[k + 1] != s2[i])
            k = pi[k];
        if (s1[k + 1] == s2[i])
            k++;
        if (k == n - 1) {
            k = pi[n - 1];
            cnt++;
            if (cnt <= 1000)
                ans[cnt] = i - n + 1;
        }
    }
    fout << cnt << '\n';
    for (int i = 1;i <= min(cnt, 1000);i++)
        fout << ans[i] << " ";
    return 0;
}