Pagini recente » Cod sursa (job #1081664) | Cod sursa (job #2284172) | Cod sursa (job #2141433) | Cod sursa (job #2978076) | Cod sursa (job #3272972)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
void make_prefix(string &a, vector<int> &p)
{
int n = a.size();
p.resize(n);
for (int i = 1; i < n; ++i)
{
int j = p[i - 1];
while (j && a[i] != a[j])
j = p[j - 1];
if (a[i] == a[j])
++j;
p[i] = j;
}
}
int count_occurences(string &a, int len, vector<int> &p)
{
int cnt = 0;
for (int i = len + 1; i < a.size(); ++i)
cnt += p[i] == len;
return cnt;
}
int main()
{
fin >> a >> b;
int len = a.size();
b = a + '#' + b;
vector<int> p;
make_prefix(b, p);
fout << count_occurences(b, len, p) << '\n';
int cnt = 1000, i = len + 1;
while (cnt && i < b.size())
{
if (p[i] == len)
{
fout << i - 2 * len << ' ';
--cnt;
}
++i;
}
return 0;
}