Pagini recente » Cod sursa (job #1304631) | Cod sursa (job #2394153) | Cod sursa (job #2577067) | Cod sursa (job #2774037) | Cod sursa (job #1008856)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int Nmax = 2000005;
vector<int> sol;
char A[ Nmax ],B[ Nmax ];
int N,M,K , prefix[ Nmax ];
void read()
{
scanf("%s\n%s",&A,&B);
N = strlen(A)-1;
M = strlen(B)-1;
}
inline void pre() {
prefix[1] = 0;
K = 0;
for(int i = 2 ; i <= N ; ++ i) {
while( K > 0 && A[K+1] != A[i])
K = prefix[K];
if(A[K+1] == A[i])
++ K;
prefix[i] = K;
}
}
inline void KMP() {
K = 0;
for(int i = 1 ; i <= M ; ++ i) {
while( K > 0 && A[K+1] != B[i])
K = prefix[K];
if(A[K+1] == B[i])
++ K;
if(K == N)
sol.push_back(i-K);
}
}
inline void print()
{
printf("%d\n",sol.size());
int x = sol.size();
for(int i = 0 ; i < min(1000,x);++i)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
pre();
KMP();
print();
return 0;
}