Pagini recente » Cod sursa (job #2767136) | Cod sursa (job #523533) | Cod sursa (job #1130212) | Cod sursa (job #2576950) | Cod sursa (job #2373745)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int DIM = 2e6 + 7;
int prefix[DIM];
string a;
string b;
vector <int> pos;
int main()
{
string a;
string b;
in >> a >> b;
int n = b.size();
int m = a.size();
a = ' ' + a;
b = ' ' + b;
int k = 0;
for(int i = 2; i <= m; i++)
{
while(k != 0 && a[k + 1] != a[i])
k = prefix[k];
if(a[k + 1] == a[i])
k++;
prefix[i] = k;
}
k = 0;
int nr = 0;
for(int i = 1; i <= n; i++)
{
while(k != 0 && a[k + 1] != b[i])
k = prefix[k];
if(a[k + 1] == b[i])
k++;
if(k == m)
{
k = prefix[m];
nr++;
if(pos.size() < 1000)
{
pos.push_back(i - m);
}
}
}
out << nr << '\n';
for(auto i : pos)
out << i << ' ';
}