Cod sursa(job #3352083)

Utilizator mtcmtcmtc mtc mtcmtc Data 23 aprilie 2026 16:26:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char a[200005],b[200005];
int ans[1005];
int pref[200005];
int main()
{
    cin>>a>>b;
    int n=strlen(a);
    int m=strlen(b);
    for(int i=1;i<n;i++){
        int j=pref[i-1];
        while(j>0&&a[i]!=a[j]){
            j=pref[j-1];
        }
        if(a[i]==a[j]) j++;
        pref[i]=j;
    }
    int j=0;
    int cnt=0;
    for(int i=0;i<m;i++){
        while(j>0&&a[j]!=b[i]){
            j=pref[j-1];
        }
        if(a[j]==b[i]){
            j++;
            if(j==n){
                cnt++;
                if(cnt<=1000){
                    ans[cnt]=i-n+1;
                }
                j=pref[j-1];
            }
        }
    }
    cout<<cnt<<'\n';
    for(int i=1;i<=min(cnt,1000);i++) cout<<ans[i]<<" ";
    return 0;
}