Pagini recente » Cod sursa (job #1548826) | Cod sursa (job #1138222) | Cod sursa (job #2445130) | Cod sursa (job #1921839) | Cod sursa (job #1143863)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int NMAX = 2e6;
char pattern[NMAX + 5], txt[NMAX + 5];
int right, p[NMAX + 5], z[NMAX + 5], n, m;
vector <int> sol;
inline void expandPattern (int start, int i) {
right = i;
do {
++ right;
}while(pattern[right] == pattern[right - start + 1] && right <= n);
-- right;
}
inline void expandTxt (int start, int i) {
right = i;
do {
++right;
}while(txt[right] == pattern[right - start + 1] && right <=m );
-- right;
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int pos, i, cnt;
gets(pattern + 1); n = strlen(pattern + 1);
gets(txt + 1); m = strlen(txt + 1);
right = 1;
for(i = 2; i <= n; ++ i) {
if(pattern[i] != pattern[1]) {
z[i] = 0;
continue;
}
if(i > right || z[i - pos + 1] + i - 1 >= right) {
pos = i;
expandPattern(pos, i);
z[i] = right - i + 1;
} else
z[i] = z[i - pos + 1];
}
right = cnt = 0;
for(i = 1 ; i <= m; ++ i) {
if(txt[i] != pattern[1]) {
p[i] = 0;
continue;
}
if(i > right || z[i - pos + 1] + i - 1 >= right) {
pos = i;
expandTxt(pos, i);
p[i] = right - i + 1;
} else
p[i] = z[i - pos + 1];
if(p[i] == n) {
++cnt;
if(sol.size() <= 1000)
sol.push_back(i);
}
}
printf("%d\n",cnt);
for(i = 0; i < sol.size() && i <= 999; ++ i)
printf("%d ",sol[i] - 1);
return 0;
}