Pagini recente » Cod sursa (job #535144) | Cod sursa (job #887062) | Cod sursa (job #2779457) | Cod sursa (job #1604264) | Cod sursa (job #1813791)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2e6 + 10;
string a, str;
int z[nmax<<2];
int cnt;
vector < int > ans;
void input() {
fin >> a >> str;
}
void run_Z(string s) {
int L, R; L = R = 1;
for (int i = 2; i < (int)s.size(); ++i) {
if (i > R) {
for (L = R = i; R < (int)s.size() && s[R] == s[R-i+1]; ++R); --R;
z[i] = R - i + 1;
}
else {
//z[i] >= min(z[i-L+1], R - i + 1)
if (z[i-L+1] < R - i + 1)
z[i] = z[i-L+1];
else {
for (L = i; R < (int)s.size() && s[R] == s[R-i+1]; ++R); --R;
z[i] = R - i + 1;
}
}
}
}
void output() {
for (int i = (int)a.size() + 1; i <= (int)a.size() + (int)str.size(); ++i)
if (z[i] >= (int)a.size()) {
cnt++;
if (cnt <= 1000) ans.push_back(i-(int)a.size()-1); //0-indexed
}
fout << cnt << '\n';
for (auto &it : ans) fout << it << ' ';
}
int main()
{
input();
run_Z(' ' + a + str);
output();
return 0;
}