Pagini recente » Cod sursa (job #1264045) | Cod sursa (job #1073657) | Cod sursa (job #2374633) | Cod sursa (job #173019) | Cod sursa (job #800856)
Cod sursa(job #800856)
#include <cstdio>
#include <cstring>
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 void read (void)
{
std::freopen("strmatch.in","r",stdin);
std::scanf("%s%s",a,b);
std::fclose(stdin);
a_length = std::strlen(a);
b_length = std::strlen(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;
}