Pagini recente » Cod sursa (job #2721112) | Cod sursa (job #2109132) | Cod sursa (job #2417797) | Cod sursa (job #676808) | Cod sursa (job #1723608)
#include <fstream>
#include <string>
#include <vector>
std::string A,B,aux;
std::vector<int> sol;
const int Nmax = 2000005;
int cnt;
int longest_p_s[Nmax];
void make_kmp_prefix(){
int q = 0;
for(int i = 2; i < A.length(); ++i){
while(q && A[i] != A[q+1])
q = longest_p_s[q];
q += A[i] == A[q+1];
longest_p_s[i] = q;
}
}
void make_kmp_match(){
int q = 0;
for(int i = 1; i <= B.length(); ++i){
while(q && B[i] != A[q+1])
q = longest_p_s[q];
q += B[i] == A[q+1];
if(q + 1== A.length()){
++cnt;
if(sol.size() < 1000)
sol.push_back(i - A.length() + 1);
q = longest_p_s[q];
}
}
}
int main()
{
std::ifstream streamIn("strmatch.in");
std::ofstream streamOut("strmatch.out");
streamIn.sync_with_stdio(false);
streamIn >> aux;
A = "#" + aux;
streamIn >> aux;
B = "#" + aux;
make_kmp_prefix();
make_kmp_match();
streamOut << cnt << "\n";
for(int i = 0; i < sol.size(); ++i)
streamOut << sol[i] << " ";
return 0;
}