Pagini recente » Cod sursa (job #1977189) | Cod sursa (job #2584020) | Cod sursa (job #380114) | Cod sursa (job #2730009) | Cod sursa (job #2843315)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 4e6 + 2;
int z[NMAX], ans[NMAX];
string a, b, S;
int mymin(int a, int b)
{
return (a < b ? a : b);
}
int main()
{
fin >> a >> b;
S = "$" + a;
S.push_back('$');
S += b;
int sz = S.size() - 1;
int L = 0, R = 0;
z[1] = sz;
for(int i = 2; i <= sz; i++) {
if(i <= R)
z[i] = mymin(z[i - L + 1], R - i + 1);
else z[i] = 0;
while(i + z[i] <= sz && S[i + z[i]] == S[z[i] + 1])
z[i]++;
if(R < i + z[i] - 1)
L = i, R = i + z[i] - 1;
}
for(int i = 2; i <= sz; i++) {
if(z[i] >= a.size())
ans[++ans[0]] = i - a.size() - 2;
}
fout << ans[0] << '\n';
for(int i = 1; i <= mymin(ans[0], 1000); i++)
fout << ans[i] << " ";
fout << '\n';
return 0;
}