Pagini recente » Cod sursa (job #1635965) | Cod sursa (job #1311139) | Cod sursa (job #3260609) | Cod sursa (job #1559490) | Cod sursa (job #3259280)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char a[2000005],b[2000005],A[2000005],B[2000005];
int n,m,sol[1005],nr,p[2000005];
int main()
{
cin>>A;
cin>>B;
n=strlen(A);
m=strlen(B);
strcpy(a+1,A);
strcpy(b+1,B);
p[1]=0;
int l=0;
for(int i=2;i<=n;i++)
{
while(l!=0 && a[i]!=a[l+1])
l=p[l];
if(a[i]==a[l+1])
l++;
p[i]=l;
}
l=0;
for(int i=1;i<=m;i++)
{
while(l!=0 && b[i]!=a[l+1])
l=p[l];
if(b[i]==a[l+1])
l++;
if(l==n)
{
nr++;
if(nr<=1000)
sol[nr]=i-l+1;
l=p[l];///nu mai putem extinde prefixul de lungime n ci vom extinde cel mai bun prefix al sau
}
}
cout<<nr<<'\n';
if(nr>1000)
nr=1000;
for(int i=1;i<=nr;i++)
cout<<sol[i]-1<<" ";
return 0;
}
///Se dau doua siruri A si B formate din litere mici si mari ale alfabetului englez si din cifre.
///Se cere gasirea tuturor aparitiilor sirului A ca subsecventa a sirului B.
///pasul 1
///pentru sirul a vom construi p[i]=lungimea maxima a unui sufix terminat la pozitia i care e totodata si prefix
///pasul 2
///vom calcula l cel mai lung sufix terminat la pozitia i din b care e prefix in a
///daca gasesc un astfel de sufix de lungime n => avem potrivire
///https://www.youtube.com/watch?v=GTJr8OvyEVQ