Pagini recente » Cod sursa (job #468402) | Cod sursa (job #2295569) | Cod sursa (job #3345781)
#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[1] = 0;
int st = 1, dr = 1;
for(int i = 2; i <= n; i++){
zfunction[i] = max(0, min(zfunction[i - st + 1], dr - i + 1));
for(; str[i + zfunction[i]] == str[zfunction[i] + 1]; ){
zfunction[i]++;
dr = i + zfunction[i] - 1;
st = 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;
}