Pagini recente » Cod sursa (job #2866320) | Cod sursa (job #1825678) | Cod sursa (job #3153139) | Cod sursa (job #1937449) | Cod sursa (job #935414)
Cod sursa(job #935414)
#include <cstdio>
const int MAX_SIZE(2000010);
const int MAX_M(1000);
char a [MAX_SIZE];
char b [MAX_SIZE];
int dp [MAX_SIZE];
int match [MAX_M];
int matches, lena, lenb;
inline int len (const char s [ ])
{
int left(0), right(MAX_SIZE - 1), middle((left + right) >> 1);
while (left < right)
{
if (s[middle])
left = middle + 1;
else
right = middle;
middle = (left + right) >> 1;
}
return middle;
}
inline void read (void)
{
std::freopen("strmatch.in","r",stdin);
std::scanf("%s\n%s\n",a,b);
std::fclose(stdin);
}
inline void print (void)
{
std::freopen("strmatch.out","w",stdout);
std::printf("%d\n",matches);
if (matches > 1000)
matches = 1000;
for (int i(0) ; i < matches ; ++i)
std::printf("%d ",match[i]);
std::putchar('\n');
std::fclose(stdout);
}
inline void compute_border (void)
{
int i(0), j(-1);
dp[0] = -1;
while (i < lena)
{
while (j >= 0 && a[i] != a[j])
j = dp[j];
++j;
++i;
dp[i] = j;
}
}
inline void KnuthMorrisPratt (void)
{
int i(0), j(0);
while (i < lenb)
{
while (j >= 0 && a[j] != b[i])
j = dp[j];
++j;
++i;
if (j == lena)
{
if (matches < 1000)
match[matches] = i - j;
j = dp[j];
++matches;
}
}
}
int main (void)
{
read();
lena = len(a);
lenb = len(b);
compute_border();
KnuthMorrisPratt();
print();
return 0;
}