Pagini recente » Cod sursa (job #3003212) | Cod sursa (job #1399639) | Cod sursa (job #526209) | Cod sursa (job #1905364) | Cod sursa (job #300504)
Cod sursa(job #300504)
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000001], b[2000001];
int i,j,m[2000001],nrsol;//,sol[1000001];
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)
{
while(b[i+j]==a[j])
{
++j;
if(j==l2)
{
++nrsol;
sol.push_back(i);
}
}
i=i+j-m[j];
if(j>0)
j=m[j];
}
}
int main ()
{
in.get(a, 2000000);
in.get();
in.get(b, 2000000);
kmppre();
kmpmain();
out<<nrsol<<"\n";
if(!sol.empty())
for(i=0;i<sol.size();i++)
out<<sol[i]<<" ";
return 0;
}