Pagini recente » Cod sursa (job #2666840) | Istoria paginii runda/helo_2018 | Cod sursa (job #1290390) | Cod sursa (job #325541) | Cod sursa (job #2170688)
#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--;
secventa1.erase(i-j);
secventa2.erase(j);
}
if(secventa1==secventa2)
identic.push_back(j);
else
identic.push_back(0);
}
strmatch();
return 0;
}