Cod sursa(job #3359527)

Utilizator chisianisChis Ianis-Alexandru chisianis Data 29 iunie 2026 15:02:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int lps[2000010];

int main()
{
FASTIO
    
    string a, b;
    fin >> a >> b;
    int n = a.length(), m = b.length();
    int k = 0;
    for(int i = 2; i <= n; i++){
	    while(k != 0 && a[k] != a[i - 1]) 
		    k = lps[k]; 
	    if(a[k] == a[i - 1]) k++;
        lps[i] = k;
    }
    vector<int> sol;
    k = 0;
    int nrs = 0;
    for(int i = 1; i <= m; i++){
        while(k != 0 && a[k] != b[i - 1])
            k = lps[k];
        if(a[k] == b[i - 1]) k++;
        if(k == n){
            sol.push_back(i - n);
            nrs++;
        }
        if(nrs == 1000) break;
    }
    fout << sol.size() << '\n';
    for(int i : sol)
        fout << i << ' ';

    return 0;
}