Pagini recente » Cod sursa (job #2881149) | Cod sursa (job #698264) | Cod sursa (job #3005140) | Cod sursa (job #274939) | Cod sursa (job #3226853)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int Nmax = 2000005;
string a, b;
int lps[Nmax];
int times_found;
vector<int> sol;
void citire(){
fin >> a >> b;
}
void init_lps(string pattern){
int len;
lps[0] = 0;
len = 0;
for(unsigned i = 1; i < a.size(); i++){
while(len > 0 && pattern[len] != pattern[i]){
len = lps[len - 1];
}
if(len == 0 && pattern[len] != pattern[i]){
lps[i] = 0;
}
else{
len++;
lps[i] = len;
}
}
}
void kmp(string a, string b){
unsigned indice_a, indice_b;
init_lps(a);
times_found = 0;
indice_a = 0;
indice_b = 0;
while((b.size() - indice_b) >= (a.size() - indice_a)){
if(b[indice_b] == a[indice_a]){
indice_a++;
indice_b++;
}
if(indice_a == a.size()){
times_found++;
if(times_found <= 1000){
sol.push_back(indice_b - indice_a);
}
indice_a = lps[indice_a - 1];
}
else if(indice_b < b.size() && a[indice_a] != b[indice_b]){
if(indice_a != 0){
indice_a = lps[indice_a - 1];
}
else{
indice_b++;
}
}
}
}
void afisare(){
fout << times_found << '\n';
for(int i = 0; i < min(times_found, 1000); i++){
fout << sol[i] << " ";
}
}
int main(){
citire();
kmp(a, b);
afisare();
return 0;
}