Cod sursa(job #2910011)

Utilizator Gica-gicutaGeorge Gica-gicuta Data 17 iunie 2022 16:37:12
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int v[2000000];
int r[2000000];
char a[2000000],b[2000000];
int main()
{
    int n=0,m=0;
    char ch;
    while(cin.get(ch))
    {
        if(ch<'A'||ch>'Z')
            break;
        m++;
        b[m]=ch;
    }
    while(cin>>ch)
    {
        n++;
        a[n]=ch;
    }
    int k=0,i,cnt=0;
    v[1]=0;
    for(i=2; i<=m; i++)
    {
        while(k>0&&b[k+1]!=b[i])
            k=v[k];
        if(b[k+1]==b[i])
            k++;
        v[i]=k;
    }
    i=0;
    for(int j=1; j<=n; j++)
    {
        while(i>0&&b[i+1]!=a[j])
            i=v[i];
        if(b[i+1]=a[j])
            i=i+1;
        if(i==m)
        {
            cnt++;
            if(cnt<=1000)
                r[cnt]=j-m+1;
        }
    }
    cout<<cnt<<'\n';
    for(int j=1; j<=cnt; j++)
    {
        if(cnt<=1000)
            cout<<r[j]-1<<" ";
        else break;
    }
    return 0;
}