Pagini recente » Cod sursa (job #1066876) | Cod sursa (job #911670) | Cod sursa (job #871334) | Cod sursa (job #360571) | Cod sursa (job #800872)
Cod sursa(job #800872)
#include <cstdio>
const int MAX_SIZE(2000001);
const int MAX_PRINT(1000);
char a [MAX_SIZE];
int a_length;
char b [MAX_SIZE];
int b_length;
int border [MAX_SIZE];
int match [MAX_PRINT];
int *add_match(match);
int matches;
inline int length (char *string)
{
int left(0), right(MAX_SIZE), middle((left + right) >> 1), length;
while (true)
{
if (middle >= MAX_SIZE)
middle = MAX_SIZE - 1;
if (string[middle])
{
length = middle + 1;
if (string[length])
left = length;
else
break;
}
else
{
length = middle - 1;
if (string[length])
break;
right = length;
}
middle = (left + right) >> 1;
}
return length;
}
inline void read (void)
{
std::freopen("strmatch.in","r",stdin);
std::scanf("%s%s",a,b);
std::fclose(stdin);
a_length = length(a);
b_length = length(b);
}
inline void print (void)
{
std::freopen("strmatch.out","w",stdout);
std::printf("%d\n",matches);
for (int *iterator(match) ; iterator < add_match ; ++iterator)
std::printf("%d ",*iterator);
std::putchar('\n');
std::fclose(stdout);
}
inline void preprocess (void)
{
*border = -1;
int i(0), j(-1);
while (i < a_length)
{
while (j >= 0 && a[i] != a[j])
j = border[j];
++i;
++j;
border[i] = j;
}
}
inline void KnuthMorrisPratt (void)
{
preprocess();
int i(0), j(0);
while (i < b_length)
{
while (j >= 0 && a[j] != b[i])
j = border[j];
++i;
++j;
if (j == a_length)
{
++matches;
if (matches <= MAX_PRINT)
{
*add_match = i - j;
++add_match;
}
j = border[j];
}
}
}
int main (void)
{
read();
KnuthMorrisPratt();
print();
return 0;
}