Pagini recente » Cod sursa (job #2880487) | Cod sursa (job #1636630) | Cod sursa (job #2055935) | Cod sursa (job #1545217) | Cod sursa (job #1698072)
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char s1[2000010], s2[2000010];
int v[1010], p[2000010], nr;
void make_prefix(char s[],int l)
{
int j=0;
for (int i = 1;i < l;)
{
if(s[i] == s[j])
p[i++] = ++j;
else if (j > 0)
j = p[j - 1];
else
p[i++] = 0;
}
}
void KMP(char s1[], char s2[])
{
int l1, l2;
l1 = strlen(s1);
l2 = strlen(s2);
make_prefix(s1, l1);
int j = 0;
for (int i = 0;i < l2;)
{
if (s1[j] == s2[i])
++i, ++j;
else if (j > 0)
j = p[j - 1];
else
++i;
if (j == l1)
{
++nr;
if (nr <= 1000)
v[nr] = i - j;
j = p[j - 1];
}
}
}
int main()
{
in >> s1 >> s2;
KMP(s1, s2);
out << nr << '\n';
for (int i = 1;i <= 1000 && i <= nr;++i)
out << v[i] << " ";
return 0;
}