Pagini recente » Cod sursa (job #2155209) | Cod sursa (job #431755) | Cod sursa (job #1690524) | Cod sursa (job #721072) | Cod sursa (job #1099519)
#include<cstdio>
#include<cstring>
#include<vector>
#define MAX 1000
#define N_MAX 2000010
#define pb push_back
using namespace std;
int Urm[N_MAX],n,m;
char A[N_MAX],B[N_MAX];
vector <int> Sol;
inline void Write_Data()
{
printf("%d\n",Sol.size());
for (vector <int> :: iterator it=Sol.begin();it!=Sol.end();++it)
printf("%d ",*it);
printf("\n");
}
inline void Next(char B[N_MAX],int m)
{
int k=-1;
Urm[0]=0;
for (int i=1;i<m;++i)
{
while (k>-1 && B[k+1]!=B[i]) k=Urm[k];
if (B[k+1]==B[i]) k++;
Urm[i]=k;
}
}
inline void Solve(char A[N_MAX],char B[N_MAX],int n,int m)
{
int k=-1;
for (int i=0;i<n;++i)
{
while (k>-1 && B[k+1]!=A[i]) k=Urm[k];
if (B[k+1]==A[i]) k++;
if (k==m-1)
{
if (Sol.size()<MAX) Sol.pb(i-m+1);
k=Urm[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(B), gets(A);
n=strlen(A), m=strlen(B);
Next(B,m);
Solve(A,B,n,m);
Write_Data();
fclose(stdin), fclose(stdout);
return 0;
}