Lỗi runtime error với một số test_case

[ho_min]

Chào mọi người, Mình bị lỗi runtime error khi submit trên codeforces. Khi test p = 10110101101101 với n = 20 chẳng hạn, thì code mình chạy vô hạn, mọi người xem giúp sai chỗ nào ạ ))

Đây là đề bài https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=4040

Cho dãy Fibo chuỗi F[0] = “0”, F[1] = “1” và F[n] = F[n-1] + F[n-2]
Đếm số lần xuất hiện của dãy bit p trong F(n)?

Đây là code của mình

  #include <iostream>
  #include <string>
  #include <list>
  #include <cstdio>

  using namespace std;

  //declare global var
  int n;
  string p;
  long long f[95];
  list<int> mylist;

  //kmp search --> error
  void searchpoint(string s, int max_index, string p){
      //failure function for kmp search
      int len = p.length();
      int* beta = new int[len];
      int b=0;
      for (int i=1; i<len; i++){
          while (b>0  &&  p[b]!=p[i]) {
              b = beta[b-1];
          }
          b = (p[i]==p[b]) ? b+1 : 0;
          beta[i] = b;
      }
      //i=1 p[1]==p[0]->false b=0 beta[1]=0;

      //kmp
      int i=0, m=0; beta[0]=0;
      int len_s = s.length();

      //test: searchpoint("101", 2, "01")
      while (m+i < len_s) {
          //if (m > max_index) break;

          if (s[m+i] == p[i]) {
              if (i == len-1) {
                  mylist.push_back(m);
              }
              else {
                  i++; continue;
              }
          }

          if (i>0) {
              m = m + i - beta[i-1];
              i = beta[i-1];
          }
          else {
              m = m+1 ; i=0;
          }
      }
      delete[] beta;
  }

  //find occur n=3 p="01"
  long long occurences(int n, string p, string *F){
      int len = p.length(); //len=2
      //spectify
      if (len==1) {
          if (p[0]=='0') {
              if (n<2) {
                  return n == 0 ? 1 : 0;
              }
              return f[n-2];
          }
          if (p[0]=='1') {
              if (n<2) {
                  return n == 0 ? 0 : 1;
              }
              return f[n-1];
          }
      }
      if (f[n] < len) return 0;

      //f[m-4] < |p| <= f[m-3]
      int m=3;
      while (f[m-3] <= len) m++;
      if (m>n) m=n; //m=3
      //saved: a: O(m-3) ; b: O(m-2)
      long long a=0, b=0;
      long long o[2];
      o[0] = 0; o[1] = 0;

      //check occur
      searchpoint(F[m], (int) f[m-1], p);
      list<int>::iterator it;
      for (it=mylist.begin(); it != mylist.end(); ++it){
      //for (int found: mylist) {
          int found = *it;
          if (found < f[m-2]) {
              if (found + len - 1 < f[m-2]) {b++;}
              else {o[0]++; }
          }
          else if (found < f[m-1]) {
              if (found + len - 1 < f[m-1]) {a++;}
              else {o[1]++; }
          }
      }
      //saved results
      for (int i=0; i<=n-m+1; i++){
          long long old_b=b;
          b = b + a + o[i%2];
          a = old_b;
      }
      return b;
  }

  int main()
  {
      string *F = new string[35];
      //compute f (length of string)
      f[0]=1; f[1]=1;
      for (int i=1; i<91; i++) f[i+1] = f[i] + f[i-1]; //cout << f[i+1];}
      //generate F (string)
      F[0]="0"; F[1]="1"; F[2]="10"; F[3]="101";
      for (int i=3; f[i-3] < 100000; i++) F[i+1] = F[i] + F[i-1];


      //input
      cin >> n >> p;
      //output
      cout << "Case 1: " << occurences(n, p, F);

      /*searchpoint("10110101", 2, "10");
      for (int found: mylist) {
          cout << found;
      }*/
      delete[] F;
      return 0;
  }

[Phong_Ky_Vo (Tao Không Ngu.)]

Hi Ho Min.
Bạn dùng công cụ debug của ide. Hoặc in ra trong mỗi vòng lặp for hoặc while để xác định vị trí lặp sau đó kiếm tra điều kiện.

[ho_min]

Cảm ơn bạn nhé, hôm qua mình đã thử rồi và tới sáng nay cũng đã tìm ra bugs:

1. mylist không để global mà để local (trong vòng lặp nói ở bug số 5)
2. bỏ // chỗ m > max_index
3. phải khởi tạo beta[0] = 0 ngay sau dòng “int* beta = new int[len];”
4. dòng “if (f[n] < len) return 0;” chuyển thành “if (n <= 30) {if (f[n] < len) return 0; }”
5. tạo vòng lặp while(cin >> n >> p) { … } để có thể có nhiều case như đề bài