Pagini recente » Cod sursa (job #115226) | Cod sursa (job #2976817) | Rating infoarena | Cod sursa (job #179103) | Cod sursa (job #3292811)
#include <bits/stdc++.h>
using namespace std;
string a,b,suport;
vector<int>sol;
int L[4000005];
void zalgorithm()
{
int best=0;
for(int i=1; i<suport.size(); i++)
{
int rightBound=best+L[best];
int j=i-best;
if(i<rightBound)
L[i]=min(L[j], rightBound-i);
while(i+L[i]<suport.size() && suport[L[i]]==suport[i+L[i]])
L[i]++;
if(i+L[i]>rightBound)
best=i;
//cout<<i<<" "<<L[i]<<'\n';
if(L[i]==a.size())
sol.push_back(i-a.size()-1);
}
}
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>a>>b;
L[0]=1;
suport+=a;
suport+='#';
suport+=b;
/// suport = a#b
zalgorithm();
cout<<sol.size()<<'\n';
for(int i=0; i<min(1000,(int)sol.size()); i++)
cout<<sol[i]<<" ";
return 0;
}