Pagini recente » Cod sursa (job #1500119) | Cod sursa (job #2136676) | Cod sursa (job #1834051) | Cod sursa (job #1774458) | Cod sursa (job #1896759)
#include <fstream>
#include <string.h>
#define NMax 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pi[NMax], pLen, sLen, answ[NMax];
char str[NMax], pattern[NMax];
void compute_pi()
{
int j = 0;
for (int i = 2; i <= pLen; i++) {
while (j != 0 && pattern[j + 1] != pattern[i])
j = pi[j];
if (pattern[j + 1] == pattern[i])
j++;
pi[i] = j;
}
}
int main()
{
f.getline(pattern + 1, NMax);
f.getline(str + 1, NMax);
sLen = strlen(str + 1);
pLen = strlen(pattern + 1);
compute_pi();
int j = 0;
for (int i = 1; i <= sLen; i++) {
while (j != 0 && pattern[j + 1] != str[i])
j = pi[j];
if (pattern[j + 1] == str[i])
j++;
if (j == pLen) {
++answ[0];
if (answ[0] < 1000)
answ[answ[0]] = i - pLen;
}
}
g << answ[0] << '\n';
for (int i = 1; i <= answ[0] && i <= 1000; i++)
g << answ[i] << ' ';
}