Pagini recente » Cod sursa (job #2157386) | Cod sursa (job #2163051) | Cod sursa (job #1473405) | Cod sursa (job #1430313) | Cod sursa (job #2937858)
#include<iostream>
#include<fstream>
#include<string>
#include<queue>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX=2000007;
int i,len,kmp[2*NMAX],siz,spat,ct,ind;
string a,b,c;
queue<int> q;
int main()
{
in>>a>>b;
c.push_back('*');
spat=a.size();
a.append(c);
a.append(b);
siz=a.size();
i=1;
len=0;
while(i<siz)
{
if(a[len]==a[i])
{
len++;
kmp[i]=len;
i++;
}
else
{
if(len==0)
{
kmp[i]=0;
i++;
continue;
}
if(len>0)
{
len=kmp[len-1];
}
}
}
for(i=spat;i<siz;i++)
{
if(kmp[i]==spat)
{
ind=i-2*spat;
q.push(ind);
ct++;
if(ct==1000)
{
//break;
}
}
}
out<<ct<<"\n";
for(i=0;i<ct;i++)
{
out<<q.front()<<" ";
q.pop();
}
}