Pagini recente » Cod sursa (job #91323) | Cod sursa (job #1131026) | Cod sursa (job #2225903) | Cod sursa (job #807634) | Cod sursa (job #2707202)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N=2000010;
int n,p[N],cnt;
char A[N],B[N];
vector<int> poz;
int main()
{
f>>(A+1)>>(B+1);
int n=strlen(A+1);
int m=strlen(B+1);
int q=0;
/// calculul functiei prefix p[i]
for(int i=2;i<=n;i++)
{
while(q>0&&A[i]!=A[q+1])
q=p[q];
if(A[i]==A[q+1])
q++;
p[i]=q;
}
/// Algoritmul KMP ( Knuth-Moriss-Pratt)
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)
poz.push_back(i-n);
}
}
g<<cnt<<'\n';
for(auto it:poz)
g<<it<<' ';
return 0;
}