Cod sursa(job #2986029)

Utilizator alinatomi14Tomita Alina alinatomi14 Data 27 februarie 2023 16:18:08
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define L long long
#define Lq set<int>::iterator
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
/*int n,i,j;
char ch,v[1000001];
int main()
{
    cin>>n;
    for(i=0; i<n; ++i)
    {
        cin>>ch,v[i]=ch;
        st1+=ch;
        p[st1]=1;
        for(j=1; j<=i-2; --j)
        {
            if(j==1)
            {
                str2a=ch;
            }
            else
            {
                string str2a;
                str2a.clear();
                str2a+=v[i-j+1];
                str2a+=str2;
            }
            cout<<str2a<<" ";
            strcpy(str2,str2a);
        }
        cout<<"\n";
    }
}*/
string a,b;
int pi[2000001],nr,v[1001];
int main()
{
    in>>a>>b;
    int n=a.size(),k=-1;
    pi[0]=0;
    for(int i=1; i<n; ++i)
    {
        while(k>-1 && a[k+1]!=a[i])
            k=pi[k];
        if(a[k+1]==a[i])
            ++k;
        pi[i]=k;
    }
    int m=b.size(),q=-1;
    for(int i=0; i<m; ++i)
    {
        while(q>-1 && a[q+1]!=b[i])
            q=pi[q];
        if(a[q+1]==b[i])
            ++q;
        if(q==n-1)
        {
            ++nr;
            if(nr<=1000)
                v[nr]=i-n+1;
        }
    }
    out<<nr<<"\n";
    for(int i=1; i<=min(nr,1000); ++i)
        out<<v[i]<<" ";
}