Pagini recente » Cod sursa (job #2614227) | Cod sursa (job #250873) | Cod sursa (job #765156) | Cod sursa (job #431304) | Cod sursa (job #3142262)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m;
char pat[2000005];
char v[2000005];
int l[2000005];
int sol[5000];
int ksol;
int pat_l;
int t_l;
void prec_l()
{
int j=0;
int i=1;
while(i<pat_l)
{
if(pat[i]==pat[j])
{
j++;
l[i]=j;
i++;
}
else
{
if(j!=0)
j=l[j-1];
else
l[j]=0,i++;
}
}
}
int main()
{
fin>>pat;
fin>>v;
pat_l = strlen(pat);
t_l = strlen(v);
prec_l();
/**for(int i=0; i<pat_l; i++)
{
fout<<l[i]<<' ';
}**/
int i=0;
int j = 0;
while (i<t_l)
{
if(v[i]==pat[j])
{
i++;
j++;
}
if(j==pat_l)
{
ksol++;
if(ksol<=1000)
sol[ksol]=i-j;
j=l[j-1];
}
else if(i <t_l && pat[j]!=v[i])
{
if(j!=0)
j=l[j-1];
else
i++;
}
}
fout<<ksol<<'\n';
for(int i=1;i<=min(ksol,1000);i++)
fout<<sol[i]<<' ';
}