Pagini recente » Cod sursa (job #2279119) | Cod sursa (job #182155) | Cod sursa (job #698503) | Cod sursa (job #616824) | Cod sursa (job #1813744)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2e6 + 10;
string a, str;
int phi[nmax];
int cnt;
vector < int > ans;
void input() {
fin >> a >> str;
a = ' ' + a; str = ' ' + str;
}
void compute_phi(string s) {
phi[1] = 0;
for (int i = 2; i < (int)s.size(); ++i) {
int k = phi[i-1];
while (k && s[k+1] != s[i])
k = phi[k];
if (s[k+1] == s[i]) k++;
phi[i] = k;
}
}
void solve(string s, string a) {
int k = 0;
for (int i = 1; i < (int)s.size(); ++i) {
while (k && a[k+1] != s[i])
k = phi[k];
if (a[k+1] == s[i]) k++;
if (k == (int)a.size() - 1) {
cnt++;
if (cnt <= 1000) ans.push_back(i - (int)a.size() + 1); //0-indexed
}
}
}
void output() {
fout << cnt << '\n';
for (auto &it : ans) fout << it << ' ';
}
int main()
{
input();
compute_phi(a);
solve(str, a);
output();
return 0;
}