Pagini recente » Cod sursa (job #3268517) | Cod sursa (job #415996) | Cod sursa (job #830271) | Cod sursa (job #3143161) | Cod sursa (job #1349261)
#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;
}
}
int m = strlen(s);
vector<int> lame;
i = 0;
j = 0;
int kkt = 0;
while(i + j < m) {
if(s[i + j] == pat[j]) {
if(j == n - 1) {
if(kkt < 1000) {
lame.push_back(i);
}
++kkt;
++i;
j = 0;
} else {
++j;
}
} else {
if(t[j] > -1) {
i += j - t[j];
j = t[j];
} else {
j = 0;
++i;
}
}
}
printf("%d\n", kkt);
kkt = kkt > 1000 ? 1000 : kkt;
for(i = 0 ; i < kkt ; ++i) {
printf("%d ", lame[i]);
}
return 0;
}