Pagini recente » Cod sursa (job #3184384) | Cod sursa (job #2208011) | Cod sursa (job #2670387) | Cod sursa (job #3133057) | Cod sursa (job #1143874)
#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;
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int pos, i, cnt;
gets(pattern); n = strlen(pattern);
gets(txt); m = strlen(txt);
right = 0;
for(i = 1; i < n; ++ i)
if(i > right) {
pos = right = i;
while(right < n && pattern[right - pos] == pattern[right])
++ right;
z[i] = right - pos;
-- right;
} else {
if(z[i - pos] + i <= right)
z[i] = z[i - pos];
else {
pos = i;
while(right < n && pattern[right - pos] == pattern[right])
++ right;
z[i] = right - pos;
-- right;
}
}
cnt = 0;
right = -1;
for(i = 0 ; i < m; ++ i) {
if(i > right) {
pos = right = i;
while(right < m && pattern[right - pos] == txt[right])
++ right;
p[i] = right - pos;
-- right;
} else {
if(z[i - pos] + i <= right)
p[i] = z[i - pos];
else {
pos = i;
while(right < m && pattern[right - pos] == txt[right])
++ right;
p[i] = right - pos;
-- right;
}
}
if(p[i] == n)
sol.push_back(i);
}
printf("%d\n",sol.size());
for(i = 0; i < sol.size() && i <= 999; ++ i)
printf("%d ",sol[i]);
return 0;
}