Pagini recente » Cod sursa (job #3345733) | Cod sursa (job #468488) | Cod sursa (job #468541) | Cod sursa (job #468528) | Cod sursa (job #3345779)
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int nmax = 4e6 + 4;
string line0, line1, str;
int n, zfunction[nmax + 2];
int where[nmax + 2];
void computezfunc(string &str){
zfunction[0] = 0;
for(int i = 2; i <= n; i++){
zfunction[i] = 0;
for(; str[i + zfunction[i]] == str[zfunction[i] + 1]; ){
zfunction[i]++;
}
}
return;
}
int main(){
in>>line0>>line1;
str = '#' + line0 + '&' + line1 + '#';
n = str.size() - 2; ///border char
computezfunc(str);
int ways = 0;
for(int i = line0.size() + 2; i <= n; i++){
if(zfunction[i] >= line0.size()){
where[++where[0]] = i - line0.size() - 2;
}
}
out<<where[0]<<"\n";
for(int i = 1; i <= min(where[0], 1000); i++){
out<<where[i]<<" ";
}; out<<"\n";
return 0;
}