Pagini recente » Statistici Vlad Marinescu Marian (vladmarinescu19) | Cod sursa (job #1432440) | Cod sursa (job #1920008)
#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
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#endif
cin.tie(0);
ios_base::sync_with_stdio(false);
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';
}