斐波那契字符串

斐波那契字符串_KMP

前言：通过这道题恶补了一下字符串匹配的知识

思路：首先就是求出菲波那切字符串，这个很简单，但是要注意递归超时的问题，可以考虑加上备忘录，或者用递推法，接下来就是匹配问题了，常规的BF会超时，所以要用KMP,

下面的代码综合了这两种方法，就当做是一个复习，。。

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 string a[3000];
  5 string array[3000];
  6 int num[3000];
  7 int num1[3000];
  8 long long int m2=0;  
  9 int next[3000];
 10 string f(int k)//递归法加备忘录 
 11 {
 12     if(k==1) return "a";
 13     if(k==2) return "b";
 14     if(k>2) {
 15         if(a[k-1]==""){
 16             a[k-1]=f(k-1);
 17         }
 18         if(a[k-2]=="")
 19         {
 20             a[k-2]=f(k-2);
 21         }
 22         a[k] = a[k-1]+a[k-2];
 23         return a[k];
 24     }
 25 }
 26 string f1(int k)//递推法 
 27 {
 28     string a1="a";
 29        string a2="b";
 30        string a3;
 31        while(true)
 32        {
 33            a3=a2+a1;
 34            a1=a2;
 35            a2=a3;
 36            k--;
 37        //    m2=a3.length();
 38            if(k<=2) return a3;
 39     }
 40 }
 41 void BF(string str1,int stra,string str2,int strb,int k,int pos)
 42 {
 43     int i=pos;
 44     int j=0;
 45     //cout << i << strb <<"---" <<endl;
 46     while(i<stra && j<strb){
 47         if(str1[i]==str2[j]){
 48             i++;
 49             j++;
 50         }else
 51         {
 52             i=i-j+1;
 53             j=0;
 54         }
 55     }
 56     if(j>=strb){
 57         num[k]++;
 58         pos=i-strb+1;
 59         if(pos<=stra-strb){
 60             BF( str1, stra, str2, strb,k, pos);
 61         }
 62     }
 63 }
 64 void get_next(string str,int stra)
 65 {
 66     int i=1;
 67     next[1]=0;
 68     int j=0;
 69     while(i<stra){
 70         if(j==0 || str[i]==str[j]){
 71             i++;
 72             j++;
 73             next[i]=j;
 74         }else{
 75             j=next[j];
 76         }
 77     }
 78 }
 79 int KMP(string a,int stra,string b,int strb,int k,int pos)
 80 {
 81     int i=pos;
 82     int j=1;
 83     while(i<stra && j<=strb){
 84         if(j==0 || a[i]==b[j-1]){
 85             i++;
 86             j++;
 87         }else{
 88             j=next[j];
 89         }
 90     }
 91     if(j>strb){
 92         num1[k]++;
 93         pos=i-strb+1;
 94     //    cout << pos << " =pos" << endl;
 95         if(pos<=stra-strb){
 96             KMP(a,stra,b,strb,k,pos);
 97         }
 98     }
 99 }
100 int main()
101 {
102     freopen("D:/Test/Test1.txt","r",stdin);
103     a[1]="a";
104     a[2]="b";
105     int k,m;
106     cin >> k >> m;
107 
108     memset(num,0,sizeof(num));
109     memset(num1,0,sizeof(num1));
110     for(int i=0;i<m;i++){
111         cin >> array[i];
112     }
113     string str=f(k);
114     cout << "------使用BF算法得到的结果-------" <<endl;
115     for(int i=0;i<m;i++){
116         BF(str,str.length(),array[i],array[i].length(),i,0);
117         cout << num[i] << " "<< endl;
118     }  
119      cout << "------使用KMP算法得到的结果-------" <<endl;
120      
121      for(int i=0;i<m;i++){
122          get_next(array[i],array[i].length());
123         KMP(str,str.length(),array[i],array[i].length(),i,0);
124         cout << num1[i] << " "<< endl;
125     }
126     return 0;
127 }