Pagini recente » Cod sursa (job #1228793) | Cod sursa (job #294309) | Cod sursa (job #1078887) | Cod sursa (job #916961) | Cod sursa (job #927290)
Cod sursa(job #927290)
#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, k;
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());
k=min(sol.size(), 1000);
for(i=0; i<k; ++i)
printf("%d ",sol[i]);
return 0;
}