Pagini recente » Cod sursa (job #2417251) | Cod sursa (job #1931588) | Cod sursa (job #2678003) | Cod sursa (job #909636) | Cod sursa (job #893678)
Cod sursa(job #893678)
#include<fstream>
#include<cstring>
#define Nmax 2000010
using namespace std;
int n, m, i, p, prefix[Nmax], sol[Nmax];
char a[Nmax], b[Nmax], as[Nmax], bs[Nmax];
int main()
{
ifstream f("strmatch.in");
ofstream h("strmatch.out");
f.getline (as, Nmax);
f.getline (bs, Nmax);
n = strlen (as);
m = strlen (bs);
for (i = 0; i < n; ++i)
a[i + 1] = as[i];
for (i = 0; i < m; ++i)
b[i + 1] = bs[i];
f.close();
p = 0;
prefix[1] = 0;
for (i = 2; i <= n; ++i)
{
while (p > 0 && a[p + 1] != a[i])
p = prefix[p];
if (a[p + 1] == a[i])
++p;
prefix[i] = p;
}
p = 0;
for (i = 1; 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[0];
sol[sol[0]] = i - n;
p = prefix[p];
}
}
h << sol[0] << '\n';
n = min (1000, sol[0]);
for (i = 1; i <= n; ++i)
h << sol[i] << " ";
h.close();
return 0;
}