Pagini recente » Cod sursa (job #2218566) | Cod sursa (job #1885262) | Cod sursa (job #1280043) | Cod sursa (job #1492545) | Cod sursa (job #1414780)
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_N = 2000005;
int N, M, ans;
int z[2 * MAX_N], sol[1002];
char T[2 * MAX_N], A[MAX_N], B[MAX_N];
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
A[0] = B[0] = T[0] = ' ';
f >> (A + 1);
f >> (B + 1);
N = strlen(A) - 1;
M = strlen(B) - 1;
for(int i = 1; i <= N; ++i) {
T[i] = A[i];
}
int L = N;
T[++L] = '#';
for(int i = 1; i <= M; ++i) {
T[++L] = B[i];
}
for(int i = 2, C = 0, R = 0; i <= L; ++i) {
if(R >= i) {
z[i] = min(z[i - C + 1], R - i + 1);
}
while(i + z[i] <= L && T[i + z[i]] == T[z[i] + 1]) {
++z[i];
}
if(z[i] == N) {
++ans;
if(ans <= 1000) {
sol[ans] = i - N - 2;
}
}
}
g << ans << "\n";
for(int i = 1; i <= min(ans, 1000); ++i) {
g << sol[i] << " ";
}
g << "\n";
f.close();
g.close();
return 0;
}