Pagini recente » Cod sursa (job #2346427) | Cod sursa (job #2385914) | Cod sursa (job #450936) | Cod sursa (job #267437) | Cod sursa (job #2170834)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
vector<int>identic,ap;
int counter;
void strmatch()
{
int poz=0,inc=0,fid=0;
while(poz<b.size())
{
bool k=1;
while(fid<a.size() && poz<b.size() && a[fid]==b[poz])
{
fid++;
k=0;
poz++;
}
if(fid==a.size())
{
counter++;
ap.push_back(inc);
fid=identic[fid-1];
inc=poz-fid;
continue;
}
if(fid>0)
fid=identic[fid-1];
if(k)
{
inc++;
poz=inc+fid ;
}
else
inc=poz-fid;
}
fout<<counter<<"\n";
if(counter<1000)
for(int i=0;i<counter;i++)
fout<<ap[i]<<" ";
else
for(int i=0;i<1000;i++)
fout<<ap[i]<<" ";
}
int main()
{
fin>>a>>b;
identic.push_back(0);
for(int i=1;i<a.size();i++)
{
if(a[identic[i-1]]==a[i])
{
identic.push_back(identic[i-1]+1);
continue;
}
int j=identic[i-1];
string secventa1,secventa2;
secventa1.append(a,i-j+1,j);
secventa2.append(a,0,j);
while(j>1 && secventa1!=secventa2)
{
j--;
if(i-j<secventa1.size())
secventa1.erase(i-j);
if(j<secventa2.size())
secventa2.erase(j);
}
if(secventa1==secventa2)
identic.push_back(j);
else
identic.push_back(0);
}
strmatch();
return 0;
}