Pagini recente » Cod sursa (job #1258087) | Cod sursa (job #2331398) | Cod sursa (job #2385318) | Cod sursa (job #676070) | Cod sursa (job #1446212)
# include <cstdio>
# include <string>
# include <iostream>
# include <cstring>
using namespace std;
# define max_size 2000000
# define max_matches 1000
class KMP
{
private:
char Text[max_size];
char Pattern[max_size];
int Prefix[max_size];
int matchesCount, matches[max_matches];
int textLength, patternLength;
public:
KMP(char text[], char pattern[])
{
for (int i = 0; i < max_size; ++i)
{
Text[i] = text[i];
Pattern[i] = pattern[i];
}
textLength = strlen(Text) - 1;
patternLength = strlen(Pattern) - 1;
}
void Compute_Prefix_function()
{
Prefix[1] = 0;
int k = 0;
for (int q = 2; q <= patternLength; ++q)
{
while (k > 0 && Pattern[k + 1] != Pattern[q])
k = Prefix[k];
if (Pattern[k + 1] == Pattern[q])
++k;
Prefix[q] = k;
}
}
void KMP_Match()
{
Compute_Prefix_function();
int q = 0;
matchesCount = 0;
for (int i = 1; i <= textLength; ++i)
{
while (q > 0 && Pattern[q + 1] != Text[i])
q = Prefix[q];
if (Pattern[q + 1] == Text[i])
++q;
if (q == patternLength)
{
matches[matchesCount++] = i - patternLength;
if (matchesCount < max_matches)
q = Prefix[q];
else
return;
}
}
}
void printSolution()
{
printf("%d\n", matchesCount);
for (int i = 0; i < matchesCount; ++i)
printf("%d ", matches[i]);
printf("\n");
}
};
char text[max_size], pattern[max_size];
int main()
{
text[0] = pattern[0] = 'a';
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", pattern + 1, text + 1);
KMP *rez = new KMP(text, pattern);
rez->KMP_Match();
rez->printSolution();
return 0;
}