Pagini recente » Cod sursa (job #1852024) | Cod sursa (job #213030) | Cod sursa (job #802291) | Cod sursa (job #1290133) | Cod sursa (job #522939)
Cod sursa(job #522939)
#include<fstream>
#include<string>
using namespace std;
#define PI_NR 2000000
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string n, m;
int pi[PI_NR];
int result[1000];
int nrResult;
void read(){
in>>n;
in>>m;
}
void makePI(){
int k = 0;
int nrN = n.length();
pi[0] = 0;
for(int i = 1; i < nrN; i++){
while( k > 0 && n[k] != n[i]){
k = pi[k - 1];
}
if(n[k] == n[i]){
k = k + 1;
}
pi[i] = k;
}
}
void showPI(){
for(int i = 0; i < n.length(); i++){
out<<pi[i] << " ";
}
}
void solveKMP(){
int nrN = n.length();
int nrM = m.length();
int k = 0;
for(int i = 0; i < nrM; i++){
while(k > 0 && n[k] != m[i]){
k = pi[k - 1];
}
if(n[k] == m[i]){
k = k + 1;
}
if(k == nrN && nrResult <= 999){
result[nrResult] = i - nrN + 1;
nrResult += 1;
}
}
}
void showResult(){
out<< nrResult<< "\n";
for(int i = 0; i < nrResult; i++){
out<< result[i]<< " ";
}
}
int main(){
read();
makePI();
//showPI();
solveKMP();
showResult();
return 0;
}