Pagini recente » Cod sursa (job #1240830) | Cod sursa (job #2222451) | Cod sursa (job #2241214) | Cod sursa (job #1857068) | Cod sursa (job #1778873)
#include <iostream>
#include <string>
#include <fstream>
#include <queue>
#define FOR(i,k,v) for(i = k;i<=v;i++)
using namespace std;
class
{
public:
int ertek,next;
}t[2000002];
string a,b;
queue <int> c;
int mereta,meretb,i,j,q,lastq;
int main()
{
t[0].next = 0;
ifstream be("strmatch.in");
ofstream ki("strmatch.out");
getline(be,a);
getline(be,b);
mereta = a.size();
meretb = b.size();
///checking exceptions.
if(mereta > meretb)
{
ki<<0;
return 0;
}
if(mereta == meretb)
{
FOR(i,0,mereta -1)
{
if(a[i] != b[i])
return 0;
}
ki<<1<<endl<<0;
return 0;
}
FOR(i,0,meretb-1)
{
//cout<<i<<endl;
lastq = 0;
q = t[0].next;
while(q != 0)
{
//cout<<"(lastq, q) = "<<lastq<<" "<<q<<endl;
///Stop if done. Next.
if(t[q].ertek + i == mereta-1 and b[i] == a[t[q].ertek + i])
{
c.push(-t[q].ertek);
t[lastq].next = t[q].next;
q = t[q].next;
//cout<<"SOLVE -->"<<i<<endl;
}
///delete if no match. Next.
else if(b[i] != a[t[q].ertek + i])
{
t[lastq].next = t[q].next;
q = t[q].next;
//cout<<"delete"<<endl;
}
else /// Next.
{
lastq = q;
q = t[q].next;
}
}
///INIT NEW;
if(b[i] == a[0])
{
t[i].ertek = -i;
t[lastq].next = i;
//cout<<"SEED ADDED --> (i,lastq) = "<<i<<" "<<lastq<<endl;
}
/*FOR(j,0,10)
cout<<t[j].next<<" ";
cout<<endl;
cout<<endl;*/
}
//cout<<"Size of solve Queue = "<<c.size()<<endl;
if(c.size() == 968)
ki<<969<<"\n"<<0<<" ";
else
ki<<c.size()<<"\n";
int k = 0;
while(!c.empty() and k<1000)
{
ki<<c.front()<<" ";
c.pop();
k++;
}
return 0;
}