Pagini recente » Cod sursa (job #592467) | Cod sursa (job #3257749) | Cod sursa (job #2050565) | Cod sursa (job #1332886) | Cod sursa (job #2365240)
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char b[20000001];
long long p[20000001], k = 0, pos[1001];
void pref()
{
int l = 0;
for (int i = 1; b[i]; i++)
{
while (l > 0 && b[i] != b[l])
l = p[l-1];
if (b[i] == b[l]) l++;
p[i] = l;
}
}
void kmp()
{
int l = 0, i = 1;
char c;
c = f.get();
while (!(c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z' || c >= '0' && c <= '9'))
c = f.get();
while (c != EOF)
{
while (l && b[l] != c)
l = p[l - 1];
if (b[l] == c) l++;
if (b[l] == 0)
pos[k++] = i - l;
i++;
c = f.get();
}
}
int main()
{
f.getline(b, 20000001);
pref();
kmp();
g << k << "\n";
k = (k < 1000 ? k : 1000);
for (int i = 0; i < k; i++)
g << pos[i] << " ";
return 0;
}