Pagini recente » Cod sursa (job #2494669) | Cod sursa (job #1606389) | Istoria paginii runda/eusebiu_oji_2006_cls9/clasament | Cod sursa (job #2254195) | Cod sursa (job #2139792)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int N = 4e6 + 5;
vector<int> ans;
int z[N];
static int zet(string &str) {
memset(z, 0x00, sizeof(int) * (str.size() + 1));
int n, l = 0, r = 0;
n = str.size();
for (int i = 1; i < n; ++i) {
if (i > r) {
for (int j = 0; j < n - i && str[j] == str[i + j]; ++j)
z[i]+= 1;
l = i;
r = i + z[i]; }
else {
z[i] = min(r - i, z[i - l]);
for (int j = z[i]; j < n - 1 && str[j] == str[i + j]; ++j)
z[i]+= 1;
if (i + z[i] > r) {
r = i + z[i];
l = i; } } }
return z[str.size() - 1]; }
int main() {
string str, pat;
fi >> pat >> str;
str = pat + "#" + str;
zet(str);
for (int i = 1; i < str.size(); ++i) if (z[i] == pat.size())
ans.push_back(i - pat.size() - 1);
fo << ans.size() << '\n';
for (int i = 0; i < 1000 && i < ans.size(); ++i)
fo << ans[i] << ' ';
fo << endl;
return 0; }