Pagini recente » Cod sursa (job #879600) | Cod sursa (job #2461697)
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
string a,b,concat;
int z[4000010];
int main()
{
ifstream t1("strmatch.in");
ofstream t2("strmatch.out");
t1>>a;
t1>>b;
concat=a+'!'+b;
cout<<concat<<'\n';
int len=a.length();
int i,l,r;
l=r=0;
int sol=0;
vector<int> poz;
for(i=1;i<concat.length();i++)
{
if(i>r)
{
l=r=i;
while(r<concat.length() && concat[r]==concat[r-l])
r++;
z[i]=r-l;
r--;
}
else
{
int k=i-l;
if( z[k] <r-i+1)
{
z[i]=z[k];
}
else
{
l=i;
r=i+z[k];
while(r<concat.length() && concat[r]==concat[r-l])
r++;
z[i]=r-l;
r--;
}
}
if(z[i]==len)
{
sol++;
poz.push_back(i-len-1);
}
}
/* for(i=0;i<concat.length();i++)
cout<<concat[i]<<' '; cout<<'\n';
for(i=0;i<concat.length();i++)
cout<<z[i]<<' '; cout<<'\n';*/
t2<<sol<<'\n';
for(auto it:poz)
t2<<it<<' '; t2<<'\n';
t1.close();
t2.close();
return 0;
}