Pagini recente » Cod sursa (job #3215887) | Cod sursa (job #18161) | Cod sursa (job #987017) | Cod sursa (job #3188) | Cod sursa (job #2984761)
#include <bits/stdc++.h>
using namespace std;
const int nmx = 2e6 + 4;
string pat,b;
int pi[nmx];
void calcPi(){
for(int i=1;i<pat.size();i++){
int j = pi[i-1];
while(j>0 && pat[i]!=pat[j])
j = pi[j-1];
if(pat[i] == pat[j])
j++;
pi[i] = j;
}
}
int main(){
cin >> pat >> b;
calcPi();
int j=0;
vector<int> m;
for(int i=0;i<b.size();i++){
while(j>0 && pat[j]!=b[i])
j = pi[j-1];
if(pat[j]==b[i])
j++;
if(j == pat.size()){
m.push_back(i-pat.size()+1);
}
}
cout << m.size() << "\n";
for(int to : m)
cout << to << " ";
}