Pagini recente » Cod sursa (job #291750) | Cod sursa (job #736427) | Cod sursa (job #748866) | Cod sursa (job #2017342) | Cod sursa (job #1833853)
#include <fstream>
#include <string.h>
#include <vector>
#define NMax 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char str[NMax], pattern[NMax], lenStr, lenPat;
int longPref[NMax], pos[1010], num;
void computeLongestPrefSuf()
{
longPref[1] = 0;
int crt = 0;
for (int i = 2; i <= lenPat; i++) {
while (crt > 0 && pattern[crt + 1] != pattern[i])
crt = longPref[crt];
if (pattern[crt + 1] == pattern[i])
crt++;
longPref[i] = crt;
}
}
void computeNumberOfOcc()
{
int posPat = 0;
for (int i = 1; i <= lenStr; i++) {
while (posPat > 0 && pattern[posPat + 1] != str[i])
posPat = longPref[posPat];
if (pattern[posPat + 1] == str[i])
posPat++;
if (posPat == lenPat) {
num++;
if (num < 1000)
pos[num] = i - lenPat;
}
}
}
int main()
{
f >> (pattern + 1);
f >> (str + 1);
lenPat = strlen(pattern + 1);
lenStr = strlen(str + 1);
computeLongestPrefSuf();
computeNumberOfOcc();
g << num << "\n";
for (int i = 1; i <= num && i <= 1000; i++)
g << pos[i] << " ";
return 0;
}