Pagini recente » Cod sursa (job #1979117) | Profil livlivi | Cod sursa (job #1799349) | Cod sursa (job #2275753) | Cod sursa (job #1008864)
#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+1),(B+1));
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;
}