Cod sursa(job #3163460)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 31 octombrie 2023 14:53:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

string s, t;

int firstSize, ans;
vector <int> pi, poz;

void kmp()
{
    for(int i = 1;i < s.size(); i ++)
    {
        int j = pi[i - 1];
        while(j  &&  s[i] != s[j])
            j = pi[j - 1];
        if(s[i] == s[j])
            pi[i] = j + 1;
        else
            pi[i] = 0;
        if(pi[i] == firstSize)
        {
            ans ++;
            poz.push_back(i - 2 * firstSize);
        }
    }
}

int main()
{
    ios_base ::sync_with_stdio(0);
    cin.tie(0);

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin >> s >> t;
    firstSize = s.size();
    s += '#';
    s += t;

    pi.resize(s.size(), 0);
    kmp();

    cout << ans << "\n";
    int endFor = min(ans, 1000);
    for(int i = 0; i < endFor; i ++)
        cout << poz[i] << " ";

    return 0;
}