Pagini recente » Cod sursa (job #2616744) | Monitorul de evaluare | Cod sursa (job #1925660) | Cod sursa (job #2378825) | Cod sursa (job #2717350)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("kmp.in");
ofstream fout("kmp.out");
const int LMax = 2 * 1e6;
vector <int> ans;
int n, m;
int table[LMax + 5];
char word[LMax + 5], str[LMax + 5];
void Read(){
fin >> word >> str;
n = strlen(word), m = strlen(str);
}
void CreateTable(){
table[0] = -1;
int i = 1, ind = 0;
while (i < n){
if (word[i] == word[ind])
table[i] = table[ind];
else{
table[i] = ind;
while (ind >= 0 && word[i] != word[ind])
ind = table[ind];
}
i++, ind++;
}
table[i] = ind;
}
void KMP(){
int i = 0, j = 0;
while (j < m){
if (word[i] == str[j]){
i++, j++;
if (i == n){
ans.push_back(j - i);
i = table[i];
}
}
else{
i = table[i];
if (i < 0)
i++, j++;
}
}
}
void Print(){
fout << ans.size() << '\n';
for (auto pos : ans)
fout << pos << ' ';
fout << '\n';
}
int main(){
Read();
CreateTable();
KMP();
Print();
return 0;
}