Pagini recente » Cod sursa (job #2190427) | Cod sursa (job #2792000) | Cod sursa (job #2708547)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream be("strmatch.in");
ofstream ki("strmatch.out");
vector<int>build_kmp(string a)
{
int na=a.length();
vector<int>t(na,0);
for(int i=1;i<na;i++)
{
int k=t[i-1];
while(true)
{
if(a[i]==a[k])
{
t[i]=k+1;
break;
}
else if(k==0)
{
t[i]=0;
break;
}
else
k=t[k-1];
}
}
return t;
}
int main()
{
string a,b;
be>>a>>b;
int na=a.length();
int nb=b.length();
auto t=build_kmp(a);
int s=0,i=0;
vector<int>poz;
while(s<nb-na+1)
{
if(i==na)
{
poz.push_back(s);
s+=i-t[i-1];
i=t[i-1];
}
else if(b[s+i]==a[i]){
i++;
}
else if(i==0)
s++;
else {
s+=i-t[i-1];
i=t[i-1];
}
}
ki<<poz.size()<<endl;
for(int i=0;i<poz.size() && i<1000;i++)
ki<<poz[i]<<" ";
return 0;
}