Pagini recente » Cod sursa (job #882236) | Cod sursa (job #1628855) | Cod sursa (job #1942395) | Cod sursa (job #2747729) | Cod sursa (job #2722885)
#include <fstream>
#include <string.h>
#define N 2000001
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, m, k;
int lps[N], aparitii[N];
char sir[N], text[N];
void creareLPS(){
int len = 0;
lps[0] = 0;
int i = 1;
while(i < n){
if(sir[i] == sir[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(sir[i] == text[j])
i++, j++;
if(i == n){
aparitii[++k] = j - i;
i = lps[i - 1];
}
else if(j < m && sir[i] != text[j]){
if(i != 0) i = lps[i - 1];
else j++;
}
}
}
int main()
{
in.getline(sir, N);
in.getline(text, N);
n = strlen(sir);
m = strlen(text);
creareLPS();
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;
}