Pagini recente » Cod sursa (job #1597358) | Cod sursa (job #1645283) | Cod sursa (job #3158527) | Cod sursa (job #2906552) | Cod sursa (job #2745917)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int maxN = 2000005;
int n, m;
char a[maxN], b[maxN];
int pref[maxN];
int poz[1001];
int cnt;
void Citire();
void KMP();
void Prefix();
void Afisare();
int main()
{
Citire();
Prefix();
KMP();
Afisare();
return 0;
}
void Citire()
{
a[0] = ' ';
b[0] = ' ';
fin >> (a+1) >> (b+1);
n = strlen(a) - 1;
m = strlen(b) - 1;
}
void Prefix()
{
pref[1] = 0;
int k = 0;
for (int i = 2; i <= n; ++i)
{
while ((k > 0) && (a[k + 1] != a[i]) )
k = pref[k];
if (a[k + 1] == a[i])
++k;
pref[i] = k;
}
}
void KMP()
{
int q = 0;
for (int i = 1; i <= m; ++i)
{
while ((q > 0) && (a[q + 1] != b[i]))
q = pref[q];
if (a[q + 1] == b[i])
++q;
if (q == n)
{
poz[i - n + 1] = 1;
cnt++;
}
}
}
void Afisare()
{
fout << cnt << '\n';
int minim = min(m, 1000);
for (int i = 1; i <= minim; ++i)
{
if(poz[i] == 1)
fout << i - 1 << ' ';
}
}