Pagini recente » Cod sursa (job #2912344) | Cod sursa (job #19981) | Cod sursa (job #106883) | Cod sursa (job #138875) | Cod sursa (job #3300525)
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int f[100005];
int g[100005];
int h[100005];
int gs[100005];
int bc[256];
string p;
string t;
int main()
{
//
fin>>p>>t;
for(int i=0;i<256;i++)
bc[i]=0;
int m=p.size();
for(int i=0;i<p.size();i++)
bc[p[i]]=i;
f[0]=-1;
for(int i=1;i<=m;i++)
{
int k=f[i-1];
while(k>=0&&p[i-1]!=p[k])
k=f[k];
f[i]=k+1;
}
for(int i=0;i<m;i++)
gs[i]=f[m]-(m-i);
reverse(p.begin(),p.end());
h[0]=-1;
for(int i=1;i<=m;i++)
{
int k=h[i-1];
while(k>=0&&p[i-1]!=p[k])
k=h[k];
h[i]=k+1;
}
for(int i=0;i<=m;i++)
g[i]=h[m-i];
for(int i=0;i<=m;i++)
gs[m-g[i]]=i;
int i=0;
int k=0;
int n=t.size();
reverse(p.begin(),p.end());
int lasti=-1;
int cnt=0;
vector <int> ans;
while(i<=n-m)
{
if(t[i+m-k-1]==p[m-k-1])
{
k++;
if(k==m)
{
if(ans.size()<1000)
{
ans.push_back(i);
}
k--;
int shiftbc=m-k-1-bc[t[i+m-k-1]];
int shiftgs=m-k-gs[m-k];
i+=max(shiftbc,shiftgs);
k=0;
}
}
else
{
int shiftbc=m-k-1-bc[t[i+m-k-1]];
int shiftgs=m-k-gs[m-k];
i+=max(shiftbc,shiftgs);
k=0;
}
}
fout<<ans.size()<<'\n';
for(int i:ans)
fout<<i<<' ';
/*if(i>n-m)
{
cout<<"prst\n";
}
else
cout<<"good\n"<<i<<'\n';
// kmp*/
/*
i=0;
k=0;
while(i<=n-m&&k<m)
{
if(t[i+k]==p[k])
k++;
else
if(k==0)
i++;
else
{
i=i+k-f[k];
k=f[k];
}
}
if(i>n-m)
cout<<"prstkmp\n";
else
cout<<"goodkmp\n"<<i<<' ';*/
return 0;
}