Cod sursa(job #3309094)

Utilizator Caleb_007Sighiartau Achim Caleb Caleb_007 Data 31 august 2025 22:38:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
//#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s[2000005];
char w[2000005];
int T[2000005],q,R[2002],k,n,m;

void prefixe()
{
    for(int i=2,q=0;i<=m;i++)
    {
        while(q && w[q+1]!=w[i]) q=T[q];
        if(w[q+1]==w[i]) q++;
        T[i]=q;
    }
}

int main()
{
    int q=0;
    cin>>w>>s; n=strlen(s),m=strlen(w);
    for(int i=n;i>0;i--) s[i]=s[i-1];
    for(int i=m;i>0;i--) w[i]=w[i-1];
    s[0]=w[0]=' ';
    prefixe();
    for(int i=1;i<=n;i++)
    {
        while(s[i]!=w[q+1] && q) q=T[q];
        if(w[q+1]==s[i]) q++;
        if(q==m)
        {
            q=T[q];
            ++k;
            if(k<=1000) R[k]=i-m;
        }
    }
    cout<<k<<endl;
    for(int i=1;i<=min(k,1000);i++) cout<<R[i]<<" ";
    return 0;
}