Pagini recente » Cod sursa (job #2136787) | Cod sursa (job #1241699) | Cod sursa (job #2351249) | Cod sursa (job #2271465) | Cod sursa (job #1936682)
#include <fstream>
#include<vector>
using namespace std;
string a,b;
int urm[2000000],k,nrsol;
vector<int> sol;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
f>>a>>b;
urm[0]=-1;k=-1;
for(int i=1; i<a.size(); i++)
{
while(k>=0 && a[k+1]!=a[i]) k=urm[k];
if(a[k+1]==a[i]) k++;
urm[i]=k;
}
k=-1;
for(int i=0; i<b.size(); i++)
{
while(k>=0 && a[k+1]!=b[i]) k=urm[k];
if(a[k+1]==b[i])k++;
if(k==a.size()-1)
{
nrsol++;
sol.push_back(i-k);
k=urm[k];
}
}
g<<nrsol<<'\n';
for(int i=0; i<min(nrsol,1000); i++)
g<<sol[i]<<' ';
return 0;
}