Pagini recente » Cod sursa (job #1170338) | Cod sursa (job #2932109) | Cod sursa (job #666865) | Cod sursa (job #2926961) | Cod sursa (job #611782)
Cod sursa(job #611782)
#include<fstream>
#include<cstring>
using namespace std;
int n,m,Urm[2000005],nrsol,sol[1005];
char T[2000005],P[2000005];
void Citire()
{
int i;
ifstream fin("strmatch.in");
fin>>P;
fin>>T;
fin.close();
n=strlen(T);
m=strlen(P);
//indexez sirurile de la 1
for(i=n;i>0;i--)
T[i]=T[i-1];
for(i=m;i>0;i--)
P[i]=P[i-1];
}
void Urmatorul(char *P)
{
int k=0,x;
Urm[1]=0;
for(x=2;x<=m;x++)
{
while(k && P[k+1]!=P[x]) k=Urm[k];
if(P[k+1]==P[x]) k++;
Urm[x]=k;
}
}
void Rezolvare()
{
int i,x=0;
Urmatorul(P);
for(i=1;i<=n;i++)
{
while(x && P[x+1]!=T[i]) x=Urm[x];
if(P[x+1]==T[i]) x++; //s-au potrivit
if(x==m) //am gasit intreg pattern-ul
{
nrsol++;
if(nrsol<=1000)
sol[nrsol]=i-m;
x=Urm[x];
}
}
}
void Afisare()
{
int i;
ofstream fout("strmatch.out");
fout<<nrsol<<"\n";
for(i=1;i<=nrsol;i++)
fout<<sol[i]<<' ';
fout<<"\n";
fout.close();
}
int main()
{
Citire();
Rezolvare();
Afisare();
return 0;
}