Pagini recente » Cod sursa (job #3330625) | Borderou de evaluare (job #1168881) | Monitorul de evaluare | Cod sursa (job #3342884) | Cod sursa (job #3359327)
#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";
int valMax=min((int)rez.size(),(int)1000);
for(int i=0;i<valMax;++i){
fout<<rez[i]-a.size()<<" ";
}
}
int main(){
string a,b;
fin>>a>>b;
calcPi(a);
solve(a,b);
return 0;
}