Pagini recente » Cod sursa (job #365232) | Cod sursa (job #2038291) | Cod sursa (job #1635959) | Cod sursa (job #196855) | Cod sursa (job #1785613)
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <cmath>
#define FOR(i,k,v) for(i = k;i<=v;i++)
using namespace std;
string a,b,c;
int i,j,q;
int mereta,meretb,meretc;
int s[2000001*2];
int solve[1000];
int counter;
void check(int i)
{
if(i > mereta and s[i] == mereta)
{
if(counter < 1000)
{
solve[counter] = i;
}
counter++;
}
}
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<<counter<< "\n";
int until = min(1000,counter);
for(int ii = 0;ii < until;ii++)
{
ki<<solve[ii]<<" ";
}
return 0;
}