Pagini recente » Cod sursa (job #2318390) | Cod sursa (job #1002587) | Cod sursa (job #376934) | Cod sursa (job #716071) | Cod sursa (job #3040288)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int max_size = 2e6 + 1;
int p[max_size], n, m;
string a, b;
void prefix ()
{
int 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 ()
{
a += '$';
b += '$';
string s;
in >> s;
a += s;
in >> s;
b += s;
n = a.size() - 1;
m = b.size() - 1;
prefix();
vector <int> ans;
int rez = 0;
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;
}