Cod sursa(job #2875765)
| Utilizator | 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]<<' ';
}
