Pagini recente » Cod sursa (job #296139) | Cod sursa (job #1502520) | Cod sursa (job #585844) | Cod sursa (job #1163370) | Cod sursa (job #1785605)
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#define FOR(i,k,v) for(i = k;i<=v;i++)
using namespace std;
string a,b,c;
queue <int> Q;
int i,j,q;
int mereta,meretb,meretc;
int s[2000001*2];
void check(int i)
{
if(i > mereta and s[i] == mereta)
{
Q.push(i - mereta - 1);
}
}
int calculate_border(int i, int j)
{
int x = 1;
while(c[i] == c[j] and i < meretc)
{
x++;
i++;
j++;
}
return x;
}
int main()
{
ifstream be("strmatch.in");
ofstream ki("strmatch.out");
getline(be,a);
getline(be,b);
mereta = a.size();
meretb = b.size();
c = a + "#" + b;
//cout<<c<<endl;
i = 1;
meretc = c.size();
s[0] = 0;
while(i < meretc)
{
if(c[i] == c[0])
{
s[i] = calculate_border(i+1,1);
check(i);
q = s[i] + i;
i++;
j = 1;
while(s[j] + i < q and i<q)
{
s[i] = s[j];
check(i);
i++;
j++;
}
}
else
{
s[i] == 0;
check(i);
i++;
}
}
/*FOR(i,0,meretc-1)
{
cout<<s[i]<<" ";
}*/
ki<<Q.size()<<endl;
int counter = 0;
while(!Q.empty() and counter < 1000)
{
counter++;
ki<<Q.front()<<" ";
Q.pop();
}
return 0;
}