Pagini recente » Cod sursa (job #1178205) | Cod sursa (job #488453) | Cod sursa (job #1080418) | Cod sursa (job #1660704) | Cod sursa (job #3137395)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N= 2000010;
int n,m,cnt,p[N];
string a,b;
vector<int> sol;
int main()
{
f>>a>>b;
n=a.size();
m=b.size();
a="*"+a;
b="*"+b;
/// calcul functia prefix pentru a
int q=0;
for(int i=2;i<=n;i++)
{
/// calculam p[i]
while(q>0&&a[i]!=a[q+1])
q=p[q];
if(a[i]==a[q+1])
q++;
p[i]=q;
}
q=0;
for(int i=1;i<=m;i++)
{
while(q>0&&b[i]!=a[q+1])
q=p[q];
if(b[i]==a[q+1])
q++;
if(q==n)
{
cnt++;
if(cnt<=1000)
sol.push_back(i-n);
}
}
g<<cnt<<'\n';
for(auto it:sol)
g<<it<<' ';
return 0;
}
//algortim KMP
// functia prefix a unui sir =
// p[i]= lungimea maxima a unui sufix pentru stringul primelor i pozitii
// care este si prefix al sirului
//
//a[===========]
//b[ [===========] ]
// st i
// n
//
// i-st+1=n
// st=i-n