Cod sursa(job #2876151)

Utilizator RK13Barbu Eduard RK13 Data 23 martie 2022 08:39:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

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

char a[2000002],b[2000002];
int sol[2000002],lps[2000002],k;
int main()
{int n,m,x;
f.getline(a+1,2000001);
f.getline(b+1,2000001);
n=strlen(a+1);
m=strlen(b+1);
for (int i=2;i<=n;i++) {x=lps[i-1];
                       while (x>0 && a[x+1]!=a[i]) x=lps[x];
                       if (a[x+1]==a[i]) x++;
                       lps[i]=x;
                      }
x=0;
for (int i=1;i<=m;i++) {while (x>0 && a[x+1]!=b[i]) x=lps[x];
                        if (a[x+1]==b[i]) x++;
                        if (x==n) sol[++k]=i-n;

                        }
g<<k<<'\n';
for (int i=1;i<=min(1000,k);i++) g<<sol[i]<<' ';
}