Pagini recente » Cod sursa (job #1499885) | Cod sursa (job #1735478) | Cod sursa (job #2242077) | Cod sursa (job #709131) | Cod sursa (job #1833922)
#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];
int longPref[NMax], pos[1010], num, lenStr, lenPat;
void computeLongestPrefSuf()
{
longPref[1] = 0;
for (int i = 2; i <= lenPat; i++) {
int crt = i - 1;
while (longPref[crt] > 0 && pattern[longPref[crt] + 1] != pattern[i])
crt = longPref[crt];
if (pattern[longPref[crt] + 1] == pattern[i])
longPref[i] = longPref[crt] + 1;
else
longPref[i] = 0;
}
}
void computeNumberOfOcc()
{
int posPat = 0;
for (int i = 1; i <= lenStr; i++) {
if (pattern[posPat] == str[i])
posPat++;
else {
while (longPref[posPat] > 0 && pattern[longPref[posPat] + 1] != str[i])
posPat = pattern[posPat];
if (pattern[longPref[posPat] + 1] == str[i])
posPat = longPref[posPat] + 1;
else
posPat = 0;
}
if (posPat == lenPat) {
num++;
if (num < 1000)
pos[++num] = i - lenPat + 1;
}
}
}
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;
}