Pagini recente » Cod sursa (job #1460851) | Cod sursa (job #128558) | Cod sursa (job #73144) | Cod sursa (job #1350266) | Cod sursa (job #2438424)
#include <fstream>
#include <string>
#include <vector>
int pi[2 + 2000000], count = 0;
std::vector<int> sol;
void piCalc(std::string s, int n) {
pi[1] = 0;
int k = 0;
for (int i = 2; i <= n; i++) {
while (k > 0 && s[k + 1] != s[i])
k = pi[k];
if (s[k + 1] == s[i])
k++;
pi[i] = k;
}
}
void solve(std::string s, std::string t, int n, int m) {
int q = 0;
for (int i = 1; i <= m; i++) {
while (q > 0 && s[q + 1] != t[i])
q = pi[q];
if (s[q + 1] == t[i])
q++;
if (q == n) {
count++;
if (count <= 1000)
sol.push_back(i - n);
}
}
}
int main() {
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string s, t;
fin >> s >> t;
int n = s.size();
int m = t.size();
s = " " + s;
t = " " + t;
piCalc(s, n);
solve(s, t, n, m);
fout << count << '\n';
for (int i : sol)
fout << i << " ";
return 0;
}