Cod sursa(job #3038661)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 27 martie 2023 17:06:18
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;


const int NMAX = 2e6 + 1;

char s[NMAX],t[NMAX]; int pi[NMAX];

void kmp()
{
    int n = strlen(s + 1),j = 0;
    for(int i = 2; i <= n ; i++)
        {
            while(j && s[i] != s[j + 1]) j = pi[j];
            if(s[i] == s[j + 1]) j++;
            pi[i] = j;
        }
}

int main() {

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

	cin.getline(s + 1,NMAX);
	cin.getline(t + 1,NMAX);

    int j = 0,cnt = 0; int n = strlen(t + 1),m = strlen(s + 1);

    kmp(); vector<int> ans = {0}; int sz = 0;

    for(int i = 1; i <= n ; i++)
        {
            while(j && t[i] != s[j + 1]) j = pi[j];
            if(t[i] == s[j + 1]) j++;
            if(j == m)
                {
                    sz++;
                    if(sz <= 1000) ans.emplace_back(i - m);
                    j = pi[m];
                }
        }

    cout << min(1000,sz); for(int i = 1; i <= min(sz,1000); i++) cout << ans[i] << " ";
    cout << '\n';
    return 0;
}