Pagini recente » Cod sursa (job #197446) | Cod sursa (job #1146127) | Cod sursa (job #1625971) | Cod sursa (job #1683632) | Cod sursa (job #883596)
Cod sursa(job #883596)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 2000010
using namespace std;
int Urm[maxn];
char T[maxn],P[maxn];
int n,m,q,i,l;
vector < int > st;
void Urmatorul()
{
int k,m,q;
m=strlen(P)-1;
Urm[1] = 0;
k = 0;
for(q=2; q<=m; ++q)
/*determina lungimea celui mai lung prefix al lui P
care este si sufix al subsirului P[1..q]*/
{
while (k>0 && P[k+1]!=P[q])
k = Urm[k];
if(P[k+1]==P[q])
++k;
Urm[q] = k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(P+1); gets(T+1); P[0]=' '; T[0]=' ';
n = strlen(T)-1;
m = strlen(P)-1;
Urmatorul();
q = 0;
for(i=1; i<=n; ++i)
{
while(q>0 && P[q+1]!=T[i]) q = Urm[q];
if (P[q+1]==T[i])
++q; /*s-a mai gasit un caracter corect*/
if (q==m)
{
st.push_back(i-m);
q = Urm[q];
}
}
l=st.size();
printf("%d\n",l);
for(i=0; i<l; ++i)
printf("%d ",st[i]);
return 0;
}