Pagini recente » Cod sursa (job #3039458) | Cod sursa (job #683727) | Cod sursa (job #3156169) | Cod sursa (job #1486816) | Cod sursa (job #3039293)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m;
string a,b;
int pi[2000005],d[2000005];
vector<int>sol;
void get_pi()
{
int k=0;
for(int i=1;i<n;i++)
{
while(a[i]!=a[k+1]&&k>0)
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
}
int main()
{
f>>a>>b;
n=a.size();
m=b.size();
get_pi();
int k=0;
for(int i=0;i<m;i++)
{
while(b[i]!=a[k]&&k)
k=pi[k-1];
if(b[i]==a[k])
k++;
if(k==n)
sol.push_back(i-n+1);
}
g<<sol.size()<<'\n';
int X=sol.size();
X=min(1000,X);
for(int i=0;i<X;i++)
g<<sol[i]<< " ";
return 0;
}