博客

参考题解：

http://blog.csdn.net/liyuanshuo_nuc/article/details/53561527

初学sam，了解下sam的概念，看题后，hash搞了好几发，都错了，就搜到了这个题解。找了几组数据测了下，才发现理解错题意了，对里面的状态的理解有点错误。

我本来错误的思路是：如果某个子串出现多次，那就计算出来每次出现的位置就好了，他单独是一个状态。如果某个子串只出现一次，就找和这个子串结束位置相同且只出现一次的子串，然后这些子串是一个状态。题目中给的样例和题目中那个表倒是全过了，但是看了题解内那个代码后，发现思路有点不一样。才发现我错了。。。字符串str=”abaaab”，按照我的思路，如果输入b,则输出 “b b 2 6”。题解代码输出”b ab 2 6”，这个状态是”b ab”这两个子串，才发现同一个状态是 子串结束位置相同且出现次数也相同。

看完题解顺便把代码复制过来了。。。。。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    int n, m;
    map<long long, string> shortest, longest;
    map<string, long long> dict;
    cin>>s>>n;
    m = s.length();
    //枚举子串的起点
    for (int i = 0; i <m ; ++i)
    {
        //j表示子串的长度
        for (int j = 1; j <= m-i ; ++j)
        {
            //找到一个子串
            string x = s.substr(i, j);
            long long st = 0;
            //然后在整个串里寻找相同的子串
            for (int k = 0; k <= m-j ; ++k)
                if( x == s.substr(k,j) )
                    //标记字符串结束位置
                    st  |= (1LL<<(k+j));

            //标记最短串
            if( shortest[st].length()==0 || j< shortest[st].length() )
                shortest[st] = x;

            //标记最长串
            if( j > longest[st].length() )
                longest[st] = x;
            dict[x] = st;
        }
    }
    for (int l = 0; l <n ; ++l)
    {
        string x;
        cin>>x;
        long long st = dict[x];
        cout<<shortest[st]<<" "<<longest[st];
        for (int i = 0; i < 50 ; ++i)
            if( (1LL<<i)&st )
                cout<<" "<<i;
        cout<<endl;
    }
    return 0;
}