Pagini recente » Cod sursa (job #1489933) | Cod sursa (job #1775374) | Cod sursa (job #2041884) | Cod sursa (job #1346874) | Cod sursa (job #2356087)
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001], b[2000001];
int p[2000001], k = 0, pos[1001];
void pref()
{
int l = 0;
for (int i = 1; b[i];)
{
if (b[i] == b[l])
{
l++;
p[i] = l;
i++;
}
else if (l)
l = p[l - 1];
else
{
p[i] = 0;
i++;
}
}
}
void kmp()
{
for (int i = 0, j = 0; a[i];)
{
if (a[i] == b[j])
i++, j++;
if (!b[j])
{
pos[k++] = i - j;
j = p[j - 1];
}
else if (a[i] && a[i] != b[j])
{
if (j) j = p[j - 1];
else i++;
}
}
}
int main()
{
f.getline(b, 2000001);
f.getline(a, 2000001);
pref();
kmp();
g << k << "\n";
k = (k < 1000 ? k : 1000);
for (int i = 0; i < k; i++)
g << pos[i] << " ";
return 0;
}