Pagini recente » Cod sursa (job #2080177) | Cod sursa (job #634407) | Cod sursa (job #2378135) | Cod sursa (job #467105) | Cod sursa (job #1099572)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
#define N_MAX 2000010
#define MAX 1000
using namespace std;
int N,M,Pr[N_MAX];
char A[N_MAX],B[N_MAX];
vector <int> Sol;
inline void Write_Data()
{
int N=Sol.size();
N=min(N,MAX);
printf("%d\n",Sol.size());
for (int i=0;i<N;++i)
printf("%d ",Sol[i]);
printf("\n");
}
inline void Solve(int N,int M)
{
int k=0;
for (int i=1;i<=M;++i)
{
while (k>0 && B[i]!=A[k+1]) k=Pr[k];
if (B[i]==A[k+1]) k++;
if (k==N) Sol.pb(i-N);
}
}
inline void Gen_Pr(int N)
{
int k=0;
Pr[1]=0, Pr[0]=0;
for (int i=2;i<=N;++i)
{
while (k>0 && A[i]!=A[k+1]) k=Pr[k];
if (A[i]==A[k+1]) k++;
Pr[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(A+1), gets(B+1);
A[0]=' ', B[0]=' ';
N=strlen(A)-1, M=strlen(B)-1;
Gen_Pr(N);
Solve(N,M);
Write_Data();
fclose(stdin);
fclose(stdout);
}