Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #3202856) | Rezultatele filtrării | Cod sursa (job #2984764)
#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);
if(m.size()==1000)
break;
}
}
cout << m.size() << "\n";
for(int to : m)
cout << to << " ";
}