Pagini recente » Cod sursa (job #2954416) | Cod sursa (job #3255972) | Cod sursa (job #761321) | Cod sursa (job #1369566) | Cod sursa (job #1150830)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define FILEIN "strmatch.in"
#define FILEOUT "strmatch.out"
#define LENMAX 2000005
int SolCount;
vector<int> sol;
char A[LENMAX], B[LENMAX];
int AL, BL;
int P[LENMAX];
void prefix() {
P[1] = 0;
for ( int i = 2, k = 0; i <= AL; i++ ) {
while ( k > 0 && A[k+1] != A[i]) {
k = P[k];
}
if (A[k+1] == A[i])
k++;
P[i] = k;
}
}
void kmp() {
prefix();
for ( int i = 1, k = 0; i <= BL; i++ ) {
while ( k > 0 && A[k+1] != B[i]) {
k = P[k];
}
if (A[k+1] == B[i])
k++;
if (k == AL) {
SolCount++;
if (SolCount <= 1000)
sol.push_back(i - AL);
}
}
}
int main() {
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
fgets(A+1, LENMAX, stdin);
fgets(B+1, LENMAX, stdin);
if (A[strlen(A+1)] == '\n')
A[strlen(A+1)] = '\0';
if (B[strlen(B+1)] == '\n')
B[strlen(B+1)] = '\0';
AL = strlen(A+1); BL = strlen(B+1);
kmp();
printf("%d\n", SolCount);
for ( int i = 0; i < sol.size(); i++ ) {
printf("%d ", sol[i]);
}
printf("\n");
return 0;
}