Pagini recente » Cod sursa (job #1092293) | Cod sursa (job #775975) | Cod sursa (job #2686229) | Cod sursa (job #718437) | Cod sursa (job #3256103)
#include <fstream>
#include <bits/stdc++.h>
#include <fstream>
#define VMAX 4000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int lps[VMAX];
string s,t;
vector<int> pozitii_sir_intampinat;
int aflare_lps(int indic,int nr_initial)
{
if(s[lps[indic-1]]==s[nr_initial])
return lps[indic-1]+1;
else
{
if(indic<=1)
return -1;
return aflare_lps(lps[indic],nr_initial);
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n,m,i,j,k,q,nr,suma,maxim,minim,len_s;
fin>>s>>t;
len_s=s.size();
s+=t;
nr=0;
for(i=1;i<s.size();i++)
{
lps[i]=aflare_lps(i,i);
if(lps[i]==-1)
{
if(s[0]==s[i])
lps[i]=1;
else
lps[i]=0;
}
if(lps[i]>=len_s)
{
nr++;
pozitii_sir_intampinat.push_back(i-2*len_s+1);
}
}
fout<<nr<<'\n';
for(i=0;i<pozitii_sir_intampinat.size();i++)
fout<<pozitii_sir_intampinat[i]<<' ';
fout<<'\n';
return 0;
}