Pagini recente » Cod sursa (job #226418) | Cod sursa (job #2433986) | Cod sursa (job #1260934) | Cod sursa (job #1352039) | Cod sursa (job #2722004)
#include <fstream>
#include <string.h>
#define N 2000001
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int lps[N], aparitii[N];
int n, m, k;
char path[N], text[N];
void crearePrefix(){
int len = 0;
lps[0] = 0;
int i = 1;
while(i < n){
if(path[i] == path[len]){
len++;
lps[i] = len;
i++;
}
else{
if(len != 0) len = lps[len - 1];
else{
lps[i] = 0;
i++;
}
}
}
}
void KMP(){
int i = 0, j = 0;
while(j < m){
if(path[i] == text[j])
i++, j++;
if(i == n){
aparitii[++k] = j - i;
i = lps[i - 1];
}
else if(j < m && path[i] != text[j]){
if(i != 0) i = lps[i - 1];
else j ++;
}
}
}
int main()
{
in.getline(path, N);
in.getline(text, N);
n = strlen(path);
m = strlen(text);
crearePrefix();
KMP();
out<<k<<'\n';
if(k > 1000) k = 1000;
for(int i = 1; i <= k; ++i)
out<<aparitii[i]<<" ";
in.close();
out.close();
return 0;
}