Pagini recente » Cod sursa (job #2790015) | Cod sursa (job #959284) | Cod sursa (job #1729395) | Cod sursa (job #2773792) | Cod sursa (job #2371815)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void precalc();
void kmp();
int n, m, nr, sol[1005], pre[2000005];
char p[2000005], s[2000005];
int main()
{
int i;
fin >> p >> s;
n = strlen(s);
m = strlen(p);
kmp();
fout << nr << '\n';
for (i = 1; i <= nr; i++)
{
if (i > 1000)
break;
fout << sol[i] << ' ';
}
fout << '\n';
return 0;
}
void precalc()
{
int i, lg = 0;
pre[0] = 0;
i = 1;
while (i < m)
{
if (p[i] == p[lg])
{
lg++;
pre[i] = lg;
i++;
}
else
{
if (lg != 0)
lg = pre[lg - 1];
else
{
lg = 0;
i++;
}
}
}
}
void kmp()
{
int i, j;
precalc();
i = j = 0;
while (i < n)
{
if (p[j] == s[i])
{
i++;
j++;
}
if (j == m)
{
nr++;
if (nr <= 1000)
sol[nr] = i-m;
j = pre[j - 1];
}
else if (i < n && p[j] != s[i])
{
if (j != 0)
j = pre[j];
else i++;
}
}
}