分享最近看到的一个不错的题目


斐波那契字符串的定义如下：

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;
}

嗯，根据5L的想法把O(L^2*log(n))写出来了。小数据对过，没有问题。真的写了发现，要处理的细节还是有很多很多的。
[解决办法]
我想到个优化。

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;
}