Pagini recente » Cod sursa (job #723090) | Monitorul de evaluare | Profil florinhaja | Cod sursa (job #1900118) | Cod sursa (job #893653)
Cod sursa(job #893653)
#include<fstream>
#include<cstring>
#define Nmax 2000010
using namespace std;
int n, m, i, p, prefix[Nmax], sol[Nmax];
char a[Nmax], b[Nmax];
int main()
{
ifstream f("strmatch.in");
ofstream h("strmatch.out");
f.getline (a, Nmax);
f.getline (b, Nmax);
n = strlen (a) - 1;
m = strlen (b) - 1;
f.close();
p = -1;
prefix[0] = 0;
for (i = 1; i <= n; ++i)
{
while (p > 0 && a[p + 1] != a[i])
p = prefix[p];
if (a[p + 1] == a[i])
++p;
prefix[i] = p + 1;
}
p = -1;
for (i = 0; i <= m; ++i)
{
while (p > 0 && a[p + 1] != b[i])
p = prefix[p];
if (a[p + 1] == b[i])
++p;
if (p == n) {
sol[++sol[0]] = i - n;
p = prefix[p];
}
}
h << sol[0] << '\n';
if (sol[0] > 1000)
sol[0] = 1000;
for (i = 1; i <= sol[0]; ++i)
h << sol[i] << " ";
h.close();
return 0;
}