分享最近看到的一个不错的题目
斐波那契字符串的定义如下：
f1 = a
f2 = b
fn = fn-1 fn-2, n>2
所以前6个斐波那契字符串是："a", "b", "ba", "bab", "babba", "babbabab"
1 对应 a
2 对应 b
3 对应 ba
现在给出1个编号m，对应一个字符串fm。再给出一些字符串，s0,s1...si，求fm中，s0,s1...si各出现了多少次。
例如：m = 6，fm = babbabab
给出的字符串为：a,b,ab,aba，其中a出现了3次，b出现了5次，ab出现了3次，aba出现了1次。
[解决办法]
写了一个求fm的程序，由打印结果，可以知道a,ba,aba等 之间的关系，
但是我还没发现规律，在这儿先UP一下．
#include <conio.h>#include <string>#include <iostream>using namespace std;string fn(string& strFn1,string& strFn2){ return strFn1.append(strFn2);}string fm(int m){ if (m==1) { return "a"; } if (m==2) { return "b"; } if(m>2) { return fn(fm(m-1),fm(m-2)); }}int main(int argc,char* argv[]){ for (int i = 2;i<10;i++) { cout<<i<<" "<<fm(i)<<endl; } getch(); return 0;}
[解决办法]
2 b
3 ba
4 bab
5 babba
6 babbabab
7 babbababbabba
8 babbababbabbababbabab
9 babbababbabbababbababbabbababbabba
求a,b,ab,aba出现了几次，是否可以转化成 对数值的计算?
a=1;
b=2;
aba=??
babbabab:a=3
babbabab:b=5
babbabab:ba=3
babbabab:aba=1
1 a 1
11 b 2
121 ba 3
1331 bab 4
14641 babba 5
15101051 babbabab 6
之间有什么关系?
[解决办法]
这要靠斐波那契树的性质吧。
1. 首先si里出现连续2个a或者连续3个b=>无解。|s|=1特解做掉。于是下面假设|s|=k>1
2. 然后枚举s的分割，s=uv，|u|,|v|>0，并计算出最小的x,y使得u是fx的后缀，v是fy的前缀。这里y好算，x会复杂一点，但是O(x)时间里应该是能算出x的，而x<=|u|,y<=|v|，所以可以在O(k)算出x,y。
3. 然后就是枚举n，计算fn是否以f[n-1]以u结尾，f[n-2]以v开头的形式包含s。如果是的话，最终答案+F[m-n+1]。这一步可以直接通过观看斐波那契树的形状，以及刚才的x,y来确定，而不用生成fn。如果没错的话对于一个确定的n可以O(1)确定是否有这种包含。
4. 当n和uv枚举完的时候答案应该就是了，复杂度O(k*k*m)=O(m*k^2)。
其中第2步我信心不足。你们来验证一下。
[解决办法]
复杂度来看我的approach还是比较接近的。第2步估计很难有啥优化余地，第3步可能可以把所有的n一起算掉，然后用矩阵乘法做答案相加，做个看上去O(k^2*log(m))的东西。不过好多细节都还待填
[解决办法]
int getminsuffix(const char* str, int len){ int cur = str[len-1] == 'a' ? 1 : 2; if(len == 1) return cur; if(len >= 2 && cur == 1) if(str[len-1] == str[len-2]) return -1; //ends with "bb" else cur = 3; //ends with "ba" char* buf = new char[len*2]; buf[0] = 'b'; buf[1] = 'a'; buf[2] = 'b'; int a = cur==3 ? 2 : 1, b = 1; int result = -1; const char* p = str+len-(cur==3?2:1/*F[cur]*/)-1; while(p >= str) { for(int i=0;i<a;i++) buf[a+b+i] = buf[i]; for(int i=a+b-1;i>=0 && p>=str;i--,p--) if(*p != buf[i]) goto error; b += a; a += b; for(int i=0;i<b;i++) buf[a+i] = buf[i]; cur += 2; } result = cur;error: delete[] buf; return result;}int getminprefix(const char* str, int len){ if(str[0] == 'a') return len==1 ? 1 : -1; if(len == 1) return 2; if(len == 2) return str[1]=='a' ? 3 : -1; int a = 1, b = 1, cur = 3; while(a+b < len) { for(int i=0;i<a && a+b+i<len;i++) if(str[i] != str[a+b+i]) return -1; int temp = a+b; b = a; a = temp; cur++; } return cur;}int solve(int m, const string& s){ int result = 0; int F[30] = {0,1}; for(int i=2;i<30;i++) F[i] = F[i-1] + F[i-2]; int k = s.length(); if(k == 1) { if(m == 1 && s[0] == 'a') return 1; return s[0] == 'b' ? F[m-1] : F[m-2]; } //assume no consecutive 2 'a's and 3 'b's for now for(int i=1;i<k;i++) { int x = getminsuffix(s.c_str(), i); int y = getminprefix(s.c_str()+i, k-i); if(x < 0 || y < 0) continue; if(y == 1) { //only f[3] will be a possible case here result += x==2 ? F[m-2] : 0; continue; } //naive sum below /*for(int j=max(x+1,y+2);j<=m;j++) if((j-x)%2 != 0) result += F[m-j+1];*/ //optimized sum int from = max(x+1, y+2); if((from-x)%2 == 0) from++; int to = m; if((from+to)%2 != 0) to--; from = m-from+1; to = m-to+1; //result is F[to]+F[to+2]+...+F[from] if(to <= from) result += F[from+1] - F[to-1]; } return result;}
[解决办法]
我想到个优化。
2. 然后枚举s的分割，s=uv，|u|,|v|>0，并计算出最小的x,y使得u是fx的后缀，v是fy的前缀。这里y好算，x会复杂一点，但是O(x)时间里应该是能算出x的，而x<=|u|,y<=|v|，所以可以在O(k)算出x,y。
这一步应该可以通过递推，在线性时间里做出所有的x,y。这个可以线性的话那整个复杂度就直接把L^2*logm变成L*logm了。如果线性能出的话，加大数据量然后只求是否是子串，或者求答案mod n，这题就很硬了。
[解决办法]
其实，L=10^4，sum L=10^5的话估计人家想要的就是L*log(m)的算法了。那也就是说刚才那个优化是可行的。等我有心情了把代码写一下
[解决办法]
这样应该对吧
string fun(int m,int t[]){ t[m]++; if(m==0) { return "a"; } if(m==1) return "b"; return fun(m-1,t)+fun(m-2,t);}int main(){ string data="babbabab",s0="a",s1="b",s2="ba"; int m=6; int* t=new int[m]; for(int j=0;j<m;j++) t[j]=0; fun(m-1,t); for(int i=0;i<m;i++) { cout<<t[i]<<endl; } return 0;}