Pagini recente » Cod sursa (job #2988703) | Cod sursa (job #1892975) | Cod sursa (job #1503473) | Cod sursa (job #2696990) | Cod sursa (job #1877647)
#include <fstream>
#include <vector>
#include <cstring>
#include <cstdlib>
#define LMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
vector<int> rez;
int F[LMAX];
vector<int> kmp(string a,string b)
{
int N=a.size();
int M=b.size();
memset(F,0,sizeof(F));
///failure function
for(int i=2;i<=M;i++)
{
int j=F[i-1];
while(1)
{
if(b[j]==b[i-1])
{F[i]=j+1;break;}
if(j==0) break;
j=F[j];
}
}
int i,j;i=j=0;
vector<int> ap;
while(1)
{
if(j==N) break;
if(b[i]==a[j])
{
i++;j++;
if(i==M)
{
ap.push_back(j-M);
if(ap.size()>=1000) return ap;
i=F[i];
}
}
else if(i==0) j++;
else i=F[i];
}
return ap;
}
int main()
{
f>>a>>b;
rez=kmp(b,a);
g<<rez.size()<<"\n";
for(auto it:rez)
g<<it<<" ";
f.close();
g.close();
return 0;
}