Cod sursa(job #3196674)

Utilizator Simon2712Simon Slanina Simon2712 Data 24 ianuarie 2024 16:28:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N=2e6;
char a[2*N+2],b[N+1];
int pi[2*N+2];
int v[1001];
int main()
{
    int aL,sL,cnt=0,i;
    fin>>a;
    fin>>b;
    aL=strlen(a);
    a[aL]='$';
    strcat(a,b);
    sL=strlen(a);
    pi[0]=-1;
    for(i=1;i<sL;i++)
    {
         pi[i]=pi[i-1];
        while(pi[i]!=-1 && a[pi[i]+1]!=a[i])
            pi[i]=pi[pi[i]];
        if(a[pi[i]+1]==a[i])
            pi[i]++;
    }
    for(i=aL+1;i<sL;i++)
    {
        if(pi[i]==aL-1)
        {
            cnt++;
            if(cnt<=1000)
                v[cnt]=i-2*aL;
        }
    }
    fout<<cnt<<'\n';
    for(i=1;i<=min(1000,cnt);i++)
        fout<<v[i]<<" ";
    return 0;
}