Cod sursa(job #2869429)

Utilizator razvanalexrotaruRazvan Alexandru Rotaru razvanalexrotaru Data 11 martie 2022 15:29:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
#define cin fin
#define cout fout
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int v[2000008],lg,j,i,lg2,cnt,ras[2000008];
char s1[2000008],s2[2000008];
int main()
{
    cin.getline(s1,2000008);
    lg=strlen(s1);
    v[0]=0;
    j=0;
    for(i=1;i<lg;i++)
    {
        while(s1[i]!=s1[j] && j!=0)
        {
            j=v[j-1];
        }
        if(s1[i]==s1[j])
        {
            j++;
            v[i+1]=j;
        }
    }
    cin.getline(s2,2000008);
    lg2=strlen(s2);
    j=0;
    for(i=0;i<lg2;i++)
    {
        while(s2[i]!=s1[j] && j!=0)
            j=v[j];
        if(s2[i]==s1[j])
            j++;
        if(j==lg)
        {
            cnt++;
            ras[cnt]=i-lg+1;
        }
    }
    cout<<cnt<<'\n';
    for(i=1;i<=cnt;i++)
        cout<<ras[i]<<" ";
    return 0;
}