Cod sursa(job #2884292)

Utilizator RobertlelRobert Robertlel Data 2 aprilie 2022 20:24:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[2000005],b[2000005];
int n,m,i,poz[2000005],p[2000005],q,cnt;


int main()
{
    f>>(a+1)>>(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    q=0;
    p[1]=0;
    for(i=2;i<=n;i++)
        {
            while(q>0&&a[q+1]!=a[i])
            {
                q=p[q];
            }
            if(a[q+1]==a[i])
            {
                q=q+1;
            }
            p[i]=q;
        }
    q=0;
    for(i=1;i<=m;i++)
    {
        while(q>0&&a[q+1]!=b[i])
        {
            q=p[q];
        }
        if(a[q+1]==b[i])
        {
            q++;
        }
        if(q==n)
        {
            if(cnt<1000)
            {
                cnt++;
            poz[cnt]=i-n+1;
            }
        }
    }
    g<<cnt<<'\n';
    for(i=1;i<=cnt;i++)
        g<<poz[i]-1<<" ";
    return 0;
}