Pagini recente » Cod sursa (job #2196811) | Cod sursa (job #532782) | Cod sursa (job #964602) | Cod sursa (job #651922) | Cod sursa (job #1896756)
#include <fstream>
#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++)
g << answ[i] << ' ';
}