Pagini recente » Cod sursa (job #1439198) | Cod sursa (job #1047516) | Cod sursa (job #3003550) | Cod sursa (job #273503) | Cod sursa (job #1216264)
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;
typedef unsigned int uint;
int fail[2000000 + 5],n,m;
char p[2000000 + 10],w[2000000 + 10];
void failure(){
uint i = 1,j = 0;
while(i < m){
if(p[i] == p[j]){
fail[i] = ++j;
i++;
}
else{
if(j != 0)
j = fail[j - 1];
else{
fail[i] = 0;
j = 0;
i++;
}
}
}
}
void kmp(){
vector<int> fin;
uint i = 0,j = 0,c = 0;
for(i = 0; i < n; ){
if(w[i] == p[j]){
j++;
i++;
}
else{
if(j != 0)
j = fail[j - 1];
else{
j = 0;
i++;
}
}
if(j == m){
c++;
if(c < 1000)
fin.push_back(i - j);
i = i - j + 1;
j = 0;
}
}
printf("%d\n",c);
for(i = 0; i < fin.size(); i++)
printf("%d ", fin[i]);
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(p,sizeof(p),stdin);
fgets(w,sizeof(w),stdin);
for(; p[m] > 0; m++);
m--;
for(; w[n] > 0; n++);
failure();
kmp();
return 0;
}