Pagini recente » Cod sursa (job #917295) | Cod sursa (job #2903386) | Cod sursa (job #365419) | Cod sursa (job #3130615) | Cod sursa (job #3258593)
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int szmax = 2000000;
string s;
string pat;
int pr[szmax + 5];
int psz;
vector <int> sol;
void precompute()
{
int l = 0;
for(int i=2;i<pat.size();i++)
{
psz=i;
/// find last matching suffix
while(l!=0 && pat[i]!=pat[l+1])
l = pr[l];
/// advance pattern length
if(pat[i]==pat[l+1])
++l;
pr[i] = l;
}
}
int nrs;
int main(){
fin>>pat;
fin>>s;
pat='#' + pat;
s='#' + s;
precompute();
int l=0;
for(int i=1;i<s.size();i++){
while(l!=0 && s[i]!=pat[l+1])
l = pr[l];
if(s[i]==pat[l+1])
++l;
if(l==pat.size()-1){
if(sol.size()<1000)
sol.push_back(i-pat.size()+1);
nrs++;
l=pr[l];
}
}
fout<<nrs<<'\n';
for(auto& i : sol)
fout<<i<<' ';
}