Pagini recente » Monitorul de evaluare | Cod sursa (job #672259) | Cod sursa (job #997793) | Cod sursa (job #1401174) | Cod sursa (job #3348757)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int mxN = 2e6 + 1;
char a[mxN], b[mxN];
int lsp[mxN], lng;
void init(){
int i = 1, j = 0;
while(a[i] != '\0'){
if(a[i] == a[j])
lsp[i++] = ++j;
else
if(!j){
lsp[i] = 0;
i++;
}else
j = lsp[j - 1];
}
lng = i;
}
int main(){
fin.getline(a, mxN);
fin.getline(b, mxN);
init();
vector<int> ans;
int i = 0, j = 0, contor = 1;
while(b[i] != '\0'){
if(a[j] == b[i]){
i++;
j++;
if(j == lng){
ans.push_back(i - j);
j = lsp[lng - 1];
}
}else{
if(!j)
i++;
else
j = lsp[j - 1];
}
}
fout << ans.size() << "\n";
for(auto x : ans)
if(contor++ <= 1000)
fout << x << " ";
}