字符串匹配（后缀数组）

假设已经求出字符串S的后缀数组点击打开链接，现在要求字符串T在字符串S中出现的位置，只要通过二分搜索就可以在O（T*logS）时间内完成。当S比较大时，比O（T+S）的算法更为高效，所以需要对同样的字符串做多次匹配时，该算法更有优势。

代码：

bool contain(string S,int *sa,string T)
{
        int a=0,b=S.length();
        while(b-a>1)
        {
               int c=(a+b)/2;
               //比较S从位置sa[c]开始长度为T的子串与T
              if(S.compare(sa[c],T.length(),T)<0)    a=c;
              else b=c;
        }

        return S.compare(sa[b],T.length(),T)==0;
}