Pagini recente » Cod sursa (job #397052) | Cod sursa (job #937157) | Cod sursa (job #1812880) | Cod sursa (job #2219655) | Cod sursa (job #1815937)
#include <bits/stdc++.h>
using namespace std;
char s[4000005];
long long counter, raspuns[1001];
int Pi[4000005];
void KMP (long long lungime, long long n)
{
for (long long i = 2; i<=n; ++i)
{
Pi[i] = Pi[i-1];
while (Pi[i] && s[Pi[i]+1] != s[i]) Pi[i] = Pi[Pi[i]];
if (s[i] == s[Pi[i]+1])
++Pi[i];
if (Pi[i] == lungime)
{
++counter;
if (counter <= 1000)
raspuns[counter] = i-2*lungime-1;
}
}
}
int main()
{
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
long long n, len;
fin >> (s+1);
len = strlen(s+1);
s[len+1] = '#';
fin >> (s+len+2);
n = strlen(s+1);
KMP(len, n);
fout << counter << '\n';
for (int i = 1; i<=counter && i <=1000; ++i)
fout << raspuns[i] << " ";
return 0;
}