Pagini recente » Cod sursa (job #758002) | Cod sursa (job #1973797) | Cod sursa (job #1187922) | Cod sursa (job #2758059) | Cod sursa (job #3161490)
#include <bits/stdc++.h>
using namespace std;
/// Z-Algorithm
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string str, pat;
vector<int> Z()
{
int n = str.size();
int l = 0, r = 0;
vector<int> z(n, 0);
for (int i = 1; i < n; ++i)
{
if (i < r)
z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && str[z[i]] == str[i + z[i]])
z[i]++;
if (i + z[i] > r)
{
r = i + z[i];
l = i;
}
}
return z;
}
int main()
{
fin >> pat >> str;
str = pat + "$" + str;
vector<int> z = Z();
vector<int> ans;
int cnt = 0;
for (int i = pat.size() + 1; i < str.size(); i++)
if (z[i] == pat.size())
{
cnt++;
if ((int)ans.size() < 1000)
ans.emplace_back(i - pat.size() - 1);
}
fout << cnt << '\n';
for (int i : ans)
fout << i << ' ';
}