Pagini recente » Cod sursa (job #1349596) | Cod sursa (job #3343701) | Borderou de evaluare (job #2361139) | Cod sursa (job #3348935) | Cod sursa (job #3348754)
#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;
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)
fout << x << " ";
}