Pagini recente » Cod sursa (job #236788) | Cod sursa (job #1658877) | Cod sursa (job #499278) | Cod sursa (job #1757663) | Cod sursa (job #1349244)
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
int t[2000010];
char pat[2000010];
char s[2000010];
using namespace std;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
t[0] = -1;
t[1] = 0;
int i, j, n;
scanf("%s", pat);
scanf("%s", s);
n = strlen(pat);
i = 2; j = 0;
while(i < n) {
if(pat[i-1] == pat[j]) {
++j;
t[i] = j;
++i;
} else if(j > 0) {
j = t[j];
} else {
t[i] = 0;
++i;
}
++i;
}
int m = strlen(s);
vector<int> lame;
i = 0;
j = 0;
while(i + j < m) {
if(s[i + j] == pat[j]) {
if(j == n - 1) {
lame.push_back(i);
++i;
j = 0;
}
++j;
} else {
if(t[j] > -1) {
i += j - t[j];
j = t[j];
} else {
j = 0;
++i;
}
}
}
printf("%d\n", lame.size());
for(int i = 0 ; i < lame.size() && i < 1000; ++i) {
printf("%d ", lame[i]);
}
return 0;
}