Cod sursa(job #2875765)

Utilizator RK13Barbu Eduard RK13 Data 22 martie 2022 12:13:27
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 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>>a>>b;
n=strlen(a);
m=strlen(b);
for (int i=1;i<n;i++) {x=lps[i-1];
                       while (x>0 && a[x]!=a[i]) x=lps[x];
                       if (a[x]==a[i]) x++;
                       lps[i]=x;
                      }
x=0;
for (int i=0;i<m;i++) {while (x>0 && a[x]!=b[i]) x=lps[x];
                        if (a[x]==b[i]) x++;
                        if (x==n) k++,sol[k]=i-n+1;

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