Pagini recente » Cod sursa (job #161203) | Cod sursa (job #427577) | Cod sursa (job #413773) | Cod sursa (job #546756) | Cod sursa (job #300572)
Cod sursa(job #300572)
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000007], b[2000007];
int i,j,m[2000010],nrsol;
vector<int> sol;
void kmppre()
{
i=0;
j=-1;
m[i]=j;
int l2=strlen(a);
while(i<=l2)
{
if(j>=0 && a[i]!=a[j])
j=m[j];
++i;
++j;
m[i]=j;
}
}
void kmpmain()
{
int l1=strlen(b);
int l2=strlen(a);
i=0;
j=0;
while(i+j<=l1)
{
if(b[i+j]==a[j])
{
++j;
if(j==l2)
{
++nrsol;
if(nrsol<=1000)
sol.push_back(i);
}
}
else{
i=i+j-m[j];
if(j>0)
j=m[j];
}
}
}
int main ()
{
in.get(a, 2000003);
in.get();
in.get(b, 2000003);
kmppre();
kmpmain();
out<<nrsol<<"\n";
if(!sol.empty())
for(i=0;i<sol.size();i++)
out<<sol[i]<<" ";
return 0;
}