Pagini recente » Cod sursa (job #590975) | Cod sursa (job #1695025) | Cod sursa (job #976718) | Cod sursa (job #1003886) | Cod sursa (job #3037801)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,nr;
char text[2000001],s[2000001];
int lps[2000001];
queue<int> q;
void createlps()
{
int i=1,j=0;
while(i<m)
{
if(s[i]==s[j])
{
lps[i]=j+1;
i++;
j++;
}
else
if(j>0)
j=lps[j-1];
else
{
lps[i]=0;
i++;
}
}
}
void kmp()
{
n=strlen(text);
m=strlen(s);
createlps();
int i=0,j=0;
while(i<n)
{
if(text[i]==s[j])
{
i++;
j++;
}
else
if(j>0)
j=lps[j-1];
else
i++;
if(j==m)
{
nr++;
if(nr<=1000)
q.push(i-j);//i-j e indexul unde l-am gasit
j=lps[j-1];
}
}
}
int main()
{
f>>s;
f>>text;
kmp();
g<<nr<<'\n';
while(q.empty()==0)
{
g<<q.front()<<" ";
q.pop();
}
return 0;
}