Pagini recente » Cod sursa (job #1309764) | Cod sursa (job #1559280) | Cod sursa (job #534189) | Cod sursa (job #2107324) | Cod sursa (job #696533)
Cod sursa(job #696533)
#include <fstream>
#include <cstring>
#define nmax 2000003
#define wmax 1000
using namespace std;
char a[2000002], b[2000002];
int pi[2000002], r[2000002];
int n, m, nr = 0;
int i, j;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(a,2000002);
f.getline(b,2000002);
n = strlen(a); m = strlen(b);
pi[0] = pi[1] = 0;
for (i = 1, j = 0; i < n; ++i)
{
while (j > 0 && a[i] != a[j]) j = pi[j];
if (a[i] == a[j]) ++j;
pi[i+1] = j;
}
for (i = j = 0; i < m; ++i)
{
while (j > 0 && a[j] != b[i]) j = pi[j];
if (a[j] == b[i]) ++j;
if (j == n)
{
if (nr < wmax)
r[nr] = i - n + 1;
++nr;
j = pi[j];
}
}
g<<nr<<"\n";
if (nr > wmax) nr = wmax;
for (i = 0; i < nr; ++i)
g<<r[i]<<" ";
return 0;}