Pagini recente » Cod sursa (job #1366274) | Cod sursa (job #1232397) | Cod sursa (job #3359028) | Cod sursa (job #3303431) | Cod sursa (job #3359325)
#pragma GCC optimize("Ofast,unroll-loops")
#include<fstream>
#include<string>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int>pi;
void calcPi(string &s){
pi.resize(s.size()+1);
pi[1]=0;
int k=0;
for(int i=2;i<=s.size();++i){
while(k != 0 && s[k] != s[i-1]) {
k = pi[k];
}
if(s[k] == s[i-1]) {
k++;
}
pi[i] = k;
}
}
void solve(string &a,string &b){
vector<int>rez;
int k=0;
for(int i = 1; i <= b.size(); i++) {
while(k != 0 && a[k] != b[i-1]) {
k = pi[k];
}
if(a[k] == b[i-1]) {
k++;
}
if(k == a.size()) {
rez.push_back(i);
}
}
fout<<rez.size()<<"\n";
for(auto i:rez){
fout<<i-a.size()<<" ";
}
}
int main(){
string a,b;
fin>>a>>b;
calcPi(a);
solve(a,b);
return 0;
}