1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <iostream>
#include <assert.h>

#include <vector>
#include "message.h"
#include "poszukiwania.h"

using namespace std;

long long result = 0;

long long KMP()
{
    vector<unsigned int> T(SignalLength() + 1, -1);
//    vector<unsigned int> T(30000000, -1);

	for(int i = 1; i <= SignalLength(); i++)
	{
		int pos = T[i - 1];
		while(pos != -1 && SignalAt(pos+1) != SignalAt(i - 1+1)) 
			pos = T[pos];
		T[i] = pos + 1;
	}

	int sp = 0, kp = 0;
	while(sp < SeqLength())
	{
		while(kp != -1 && (kp == SignalLength() || SignalAt(kp+1) != SeqAt(sp+1))) kp = T[kp];
		kp++;
		sp++;
		if(kp == SignalLength()) 
			result++;
	}
	
	return result;
}


unsigned int YAdapt(unsigned int pos) //smaler
{
	return SeqAt(pos+1);
}

unsigned int XAdapt(unsigned int pos)
{
	return SignalAt(pos+1);
}


#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

//y bigger n-size
//x smalle m-size

// x -> XAdapt
// y -> Yadapt

long long KR() 
{
   int d, hx, hy, i, j;

   int m = SignalLength();//mniejszy
   int n = SeqLength(); //wiekszy

   result=0;

   /* Preprocessing */
   /* computes d = 2^(m-1) with
      the left-shift operator */
   for (d = i = 1; i < m; ++i)
      d = (d<<1);

   for (hy = hx = i = 0; i < m; ++i) {
//      hx = ((hx<<1) + x[i]);
  //    hy = ((hy<<1) + y[i]);
      hx = ((hx<<1) + XAdapt(i));
      hy = ((hy<<1) + YAdapt(i));
   }

   /* Searching */
   j = 0;
   while (j < n-m) {
      if (hx == hy)
	  {
			int jp;
			for (jp = 0; jp < m; jp++)
            {
                if (YAdapt(j + jp) != XAdapt(jp))
                    break;
            }
            if (jp == m)  
            {
                result++;
            }
	  }
      hy = REHASH(YAdapt(j), YAdapt(j + m), hy);
      ++j;
   }

   return result;
}

int main()
{
  if (MyNodeId() == 0) 
  {
	  int sl = SignalLength();
	  if (sl< 30000001)
		  cout << KMP() << endl;
	  else
		  cout << KR() << endl;
  }

  return 0;
}