Pagini recente » Cod sursa (job #1466489) | Cod sursa (job #313039) | Cod sursa (job #1215612) | Cod sursa (job #1624549) | Cod sursa (job #1513084)
#include <fstream>
#include <string.h>
#define NMax 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int strl, patl, prefsuf[NMax], sol[1010], k;
char str[NMax], pattern[NMax];
void find_prefsuf()
{
int j=0;
prefsuf[1] = 0;
for (int i = 2; i <= patl; i++) {
while (j > 0 && pattern[i] != pattern[j+1])
j = prefsuf[j];
if (pattern[i] == pattern[j+1])
j++;
prefsuf[i] = j;
}
}
int main()
{
f>>(pattern+1)>>(str+1);
strl = strlen(str+1);
patl = strlen(pattern+1);
find_prefsuf();
int j=0;
for (int i=1; i <= strl; i++) {
while (j > 0 && pattern[j+1] != str[i])
j = prefsuf[j];
if (pattern[j+1] == str[i])
j++;
if (j == patl) {
if (k <= 1000)
sol[k] = i - j;
k++;
}
}
g << k << "\n";
for (int i=1; i<=k && i <= 1000; i++)
g << sol[i] << " ";
return 0;
}