Pagini recente » Cod sursa (job #3213948) | Cod sursa (job #2960588) | Cod sursa (job #1760941) | Cod sursa (job #2123102) | Cod sursa (job #2391083)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N = 2000010;
char a[N],b[N];
int n,m,pr[N],nrPotriviri;
void prefix(),kmp();
vector<int> sol;
int main()
{
char *p=a+1,*q=b+1;
f>>p>>q;
n=strlen(p);
m=strlen(q);
prefix();
kmp();
g<<nrPotriviri<<'\n';
for(auto it:sol)
g<<it<<' ';
return 0;
}
void prefix()
{
int q=0;
for(int i=2;i<=n;i++)
{
while(q>0&&a[q+1]!=a[i])q=pr[q];
if(a[q+1]==a[i])q++;
pr[i]=q;
}
}
void kmp()
{
int q=0;
for(int i=1;i<=m;i++)
{
while(q>0&&a[q+1]!=b[i])q=pr[q];
if(a[q+1]==b[i])q++;
if(q==n)
{
nrPotriviri++;
if(nrPotriviri<=1000)
sol.push_back(i-n);
}
}
}