Pagini recente » Cod sursa (job #1369559) | Cod sursa (job #19220) | Cod sursa (job #1915836) | Cod sursa (job #976612) | Cod sursa (job #3155784)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int max_size = 2e6 + 1;
string a, b;
int p[max_size];
vector <int> ans;
void kmp ()
{
int n = a.size() - 1, q = 0;
for (int i = 2; i <= n; ++i)
{
while (q > 0 && a[q + 1] != a[i])
{
q = p[q];
}
if (a[q + 1] == a[i])
{
q++;
}
p[i] = q;
}
}
int main ()
{
in >> a >> b;
int n = a.size(), m = b.size(), rez = 0;
a = '$' + a;
b = '$' + b;
kmp();
int q = 0;
for (int i = 1; i <= m; i++)
{
while (q > 0 && a[q + 1] != b[i])
{
q = p[q];
}
if (a[q + 1] == b[i])
{
q++;
}
if (q == n)
{
rez++;
if (rez <= 1000)
{
ans.push_back(i - n);
}
}
}
out << rez << '\n';
for (auto f : ans)
{
out << f << " ";
}
in.close();
out.close();
return 0;
}