Pagini recente » Cod sursa (job #1591737) | Cod sursa (job #1742687) | Cod sursa (job #3212329) | Cod sursa (job #3281485) | Cod sursa (job #3292803)
#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]+1<suport.size() && suport[L[i]+1]==suport[i+L[i]+1])
L[i]++;
if(i+L[i]>rightBound)
best=i;
//cout<<i<<" "<<L[i]<<'\n';
if(L[i]==a.size()-1 && sol.size()<1000)
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<sol.size(); i++)
cout<<sol[i]<<" ";
return 0;
}