Pagini recente » Cod sursa (job #746272) | Cod sursa (job #2324530) | Cod sursa (job #1205435) | Cod sursa (job #1496938) | Cod sursa (job #1920001)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 2000000;
char A[2 * kMaxN + 2], B[kMaxN + 1];
int Z[2 * kMaxN + 1];
int main() {
#ifdef INFOARENA
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
#endif
cin >> A >> B;
int n = strlen(A);
A[n] = '#';
memcpy(A + n + 1, B, sizeof B);
int st = 0, fn = 0;
int stringSize = n + 1 + strlen(B);
for(int i = 1; i < stringSize; ++i) {
if(i <= fn) Z[i] = min(Z[i - st], fn - i + 1);
while(A[i + Z[i]] == A[Z[i]])
++Z[i];
if(i + Z[i] - 1 > fn) {
fn = i + Z[i] - 1;
st = i;
}
}
int answerCount = 0;
vector<int> answer;
answer.reserve(1000);
for(int i = n + 1; i < stringSize; ++i)
if(Z[i] == n) {
answerCount++;
if(answerCount <= 1000)
answer.push_back(i - n - 1);
}
cout << answerCount << '\n';
for(const int& x: answer)
cout << x << ' ';
cout << '\n';
}