Pagini recente » Cod sursa (job #1880057) | Cod sursa (job #1825008) | Cod sursa (job #607760) | Cod sursa (job #841349) | Cod sursa (job #798585)
Cod sursa(job #798585)
#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 partial [MAX_SIZE];
int output [MAX_PRINT];
int *add_match(output);
int matches;
inline int length (char *string)
{
int length, left(0), right(MAX_SIZE), middle((left + right) >> 1);
while (true)
{
if (string[middle])
{
left = middle + 1;
if (!string[left])
{
length = left + 1;
break;
}
}
else
{
right = middle;
if (string[middle - 1])
{
length = middle;
break;
}
}
middle = (left + right) >> 1;
}
}
inline void read (void)
{
std::freopen("strmatch.in","r",stdin);
std::scanf("%s%s",a,b);
a_length = length(a);
b_length = length(b);
std::fclose(stdout);
}
inline void print (void)
{
std::freopen("strmatch.out","w",stdout);
std::printf("%d\n",matches);
for (int *iterator(output) ; iterator < add_match ; ++iterator)
std::printf("%d ",*iterator);
std::putchar('\n');
std::fclose(stdout);
}
inline void partial_match (void)
{
*partial = -1;
partial[1] = 0;
int prefix(0), index(2);
while (index < a_length)
{
if (a[index - 1] == a[prefix])
{
++prefix;
partial[index] = prefix;
++index;
}
else if (prefix > 0)
prefix = partial[prefix];
else
++index;
}
}
inline void KnuthMorrisPratt (void)
{
int a_index(0), b_index(0);
while (b_index + a_index < b_length)
{
if (a[a_index] == b[b_index + a_index])
{
++a_index;
if (a_index == a_length)
{
++matches;
if (matches <= MAX_PRINT)
{
*add_match = b_index;
++add_match;
}
a_index = 0;
++b_index;
}
}
else
{
b_index = b_index + a_index - partial[a_index];
if (partial[a_index] > 0)
a_index = partial[a_index];
else
a_index = 0;
}
}
}
int main (void)
{
read();
partial_match();
KnuthMorrisPratt();
print();
return 0;
}