Pagini recente » Clasament 23 | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #855322) | Cod sursa (job #2984768)
#include <bits/stdc++.h>
using namespace std;
const int nmx = 2e6 + 4;
string pat,b;
int pi[nmx];
#if 1
#define cin fin
#define cout fout
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#endif
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 i=0;i<min(m.size(),1000U);i++)
cout << m[i] << " ";
}