Pagini recente » Cod sursa (job #29599) | Cod sursa (job #3192415) | Cod sursa (job #572972) | Cod sursa (job #857320) | Cod sursa (job #1833918)
#include <fstream>
#include <string.h>
#define NMax 2000010
using namespace std;
ifstream f("FA.in");
ofstream g("FA.out");
char pattern[NMax], str[NMax], longPref[NMax];
int patLen, strLen, pos[1010], numOc;
void constructPrefSuf()
{
int crt = 0;
for (int i = 1; i <= patLen; i++) {
while (crt > 0 && pattern[longPref[crt] + 1] != pattern[i])
crt = pattern[crt];
if (pattern[longPref[crt] + 1] != pattern[i])
crt++;
longPref[i] = crt;
}
}
int getNextState(int crtState, char transitionChar)
{
int crt = 0;
while (crt > 0 && pattern[longPref[crt] + 1] != transitionChar)
crt = pattern[crt];
if (pattern[longPref[crt] + 1] != transitionChar)
crt++;
return crt;
}
void searchForPattern()
{
int crtState = 0;
for (int i = 1; i <= strLen; i++) {
crtState = getNextState(crtState, str[i]);
if (crtState == patLen + 1) {
numOc++;
if (numOc <= 1000)
pos[numOc] = i - patLen;
}
}
}
int main()
{
f >> (pattern + 1);
f >> (str + 1);
patLen = strlen(pattern + 1);
strLen = strlen(str + 1);
searchForPattern();
g << numOc << "\n";
for (int i = 1; i <= numOc && i <= 1000; i++)
g << pos[i] << " ";
}