Pagini recente » Cod sursa (job #2123565) | Cod sursa (job #2723773) | Cod sursa (job #270124) | Cod sursa (job #2832399) | Cod sursa (job #927286)
Cod sursa(job #927286)
#include<cstdio>
#include<cstring>
#include<vector>
#define nMax 2000010
#define mMax 2000010
using namespace std;
vector <int> sol;
int Urm[mMax];
char T[nMax], P[mMax];
int n, m;
int min(int a, int b)
{
if(a<b) return a;
return b;
}
void Urmatorul(char *P)
{
int k=-1, x;
Urm[0]=0;
for(x=1; x<m; ++x)
{
while(k>0 && P[k+1]!=P[x]) k=Urm[k];
if(P[k+1] == P[x]) k++;
Urm[x]=k;
}
}
int main()
{
int i, x=-1;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(P); gets(T);
n=strlen(T); m=strlen(P);
Urmatorul(P);
for(i=0; i<n; ++i)
{
while(x>0 && P[x+1]!=T[i]) x=Urm[x];
if(P[x+1] == T[i]) x++;
if(x == m-1)
{
sol.push_back(i-m+1);
x=Urm[x];
}
}
printf("%d\n",sol.size());
for(i=0; i<min(sol.size(),999); ++i)
printf("%d ",sol[i]);
return 0;
}