Pagini recente » Cod sursa (job #286415) | Cod sursa (job #3203795) | Cod sursa (job #2882116) | Cod sursa (job #2248660) | Cod sursa (job #2820700)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
int pi[2000005],sol;
vector<int>v;
int main()
{
in >> a >> b;
a.push_back(' ');
b.push_back(' ');
int n = a.size(),m = b.size();
for (int i = n; i >= 1; i--)
a[i] = a[i - 1];
for (int i = m; i >= 1; i--)
b[i] = b[i - 1];
int k = 0;
pi[1] = 0;
for (int i = 2; i <= n; i++)
{
while (k > 0 and a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])
k++;
pi[i] = k;
}
k = 0;
for (int i = 1; i <= m; i++)
{
while (k > 0 and a[k + 1] != b[i])
k = pi[k];
if (a[k + 1] == b[i])
k++;
if (k == n - 1)
{
sol++;
if (v.size() < 1000)
v.push_back(i - n + 1);
}
}
out << sol << '\n';
for (int i = 0; i < v.size(); i++)
out << v[i] << " ";
return 0;
}