Pagini recente » Cod sursa (job #2907579) | Cod sursa (job #1296481) | Cod sursa (job #1458047) | Cod sursa (job #1041531) | Cod sursa (job #580856)
Cod sursa(job #580856)
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define LIMIT 0x200000
char Text[LIMIT];
char Pattern[LIMIT];
int Prefix[LIMIT];
int LenT, LenP;
void PreProcess()
{
Prefix[0] = -1;
int pos = 2, cnd = 0;
while (pos < LenP)
{
if (Pattern[pos-1] == Pattern[cnd])
{
cnd++; Prefix[pos] = cnd; pos++;
}
else if (cnd > 0) cnd = Prefix[cnd];
else { Prefix[pos] = 0; pos++; }
}
}
int main()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
fgets(Pattern, LIMIT, stdin);
fgets(Text, LIMIT, stdin);
LenT = strlen(Text); LenP = strlen(Pattern);
PreProcess();
int m = 0, i=0;
queue<int> FoundMatches;
while (m + i < LenT)
{
if (Pattern[i] == Text[m + i])
{
i++;
if (i == LenP-1) {
FoundMatches.push(m);
}
}
else {
m = m + i - Prefix[i];
if (Prefix[i] > -1) i = Prefix[i];
else i = 0;
}
}
printf("%d\n", FoundMatches.size());
for (int i=0; i<1000 && !FoundMatches.empty(); i++, FoundMatches.pop())
printf("%d ", FoundMatches.front());
return 0;
}