Pagini recente » Cod sursa (job #729160) | Cod sursa (job #3241974) | Cod sursa (job #700516) | Borderou de evaluare (job #1496818) | Cod sursa (job #1552501)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2000000 + 10;
int ans , N , M;
int phi[Nmax];
vector < int > v;
string a , b;
void makePhi()
{
int k;
phi[1] = 0;
for (int i = 2; i <= N; ++i)
{
k = phi[i-1];
while (k && a[i] != a[k+1])
k = phi[k];
phi[i] = (a[i] == a[k+1]) ? k + 1 : 0;
}
}
void makeKmp()
{
int k = 0;
for (int i = 1; i <= M; ++i)
{
while (k && b[i] != a[k+1])
k = phi[k];
if (b[i] == a[k+1]) k++;
if (k == N)
{
ans++;
if (ans < 1000) v.push_back(i-N);
}
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> a; a = ' ' + a + '$';
fin >> b; b = ' ' + b;
N = a.size() - 2; M = b.size() - 1;
//cerr << a << ' ' << b;
makePhi(); makeKmp();
fout << ans << '\n';
for (auto &it : v)
fout << it << ' ';
fout << '\n';
return 0;
}