0

我在解决

https://www.spoj.com/problems/BEADS/

SPOJ 的上述问题。我在下面陈述了相关信息：

问题陈述：项链的描述是一个字符串 A = a1a2 ... am 指定特定珠子的大小，其中最后一个字符 am 被认为以循环方式在字符 a1 之前。当且仅当字符串 aiai+1 ... ana1 ... ai-1 在词典上小于字符串 ajaj+1 ... ana1 ... aj 时，才说不相交点 i 比不相交点 j 差-1。字符串 a1a2 ... an 在字典上小于字符串 b1b2 ... bn 当且仅当存在整数 i，i <= n，因此 aj=bj，对于每个 j，1 <= j < i 和 ai <双。

输出：对于每个测试用例，只打印一行只包含一个整数 - 珠子的编号，它是最坏可能不相交时的第一个，即这样的 i，字符串 A[i] 在所有可能的 n 中按字典顺序最小项链脱节。如果有多个解决方案，则打印具有最低 i 的解决方案。

现在解决方案是使用 SUFFIX ARRAY。输入字符串 s，并与自身连接， s'=s+s ，因为我必须对数组的循环后缀进行排序。然后在s'上创建一个后缀数组，输出指向原始s的后缀的最小索引，即index < len(s)。

但是我面临一个问题。我在附加 '$' 字符以获得 SA，但我得到了错误的答案。在网上查找后，我找到了 1 个将“}”附加到字符串的解决方案。我发现 ascii('$') < ascii('a') < ascii('z') < ascii('}')

但我不明白这将如何产生影响，为什么这是被接受的答案并且还没有发现这会产生影响的案例。解决方案（AC）可以在这里找到：

链接到代码

    #include <bits/stdc++.h>
using namespace std;

string s;int n;
bool cmp_init(int a, int b)
{
    return s[a]<s[b] || (s[a]==s[b] && a<b);
}

int jmp;
vector<int> pos;
bool cmp(int a, int b)
{
    return pos[a]<pos[b] || (pos[a]==pos[b] && pos[(a+jmp)%n]<pos[(b+jmp)%n]);
}

int main() {
    int tc;cin>>tc;
    while(tc--){
    cin>>s;
    int m=s.size();
    s=s+s+"{";
    n=s.size();
    
    vector<int> SA(n,0);
    for(int i=0;i<n;i++)SA[i]=i;
    sort(SA.begin(), SA.end(), cmp_init);
    pos.assign(n,0);
    
    for(int i=1 , c=0;i<n;i++)pos[SA[i]]=(s[SA[i]]==s[SA[i-1]])?c:++c;
        
    for(jmp=1;jmp<=n;jmp*=2)
    {
        
        sort(SA.begin(), SA.end(), cmp);
        
        vector<int> tmp(n,0);
    
        for(int i=1 , c=0;i<n;i++)tmp[SA[i]]=(pos[SA[i]]==pos[SA[i-1]] && pos[(SA[i]+jmp)%n]==pos[(SA[i-1]+jmp)%n])?c:++c;

        for(int i=0;i<n;i++)pos[i]=tmp[i];

    }
    
        for(int i=0;i<n;i++)if(SA[i]<m){cout<<SA[i]+1<<"\n";break;}
    }
    
}

PS.：我发现 SA 构造代码是正确的，唯一的问题是最后一个字符附加。通常我们在 SA 构造中附加“$”。

4

1 回答 1

0

区别在于最后一个条件：

如果有多个解决方案，则打印具有最低 i 的解决方案。

考虑输入"abab"。

正确答案是 0，当您附加 '}' 时会得到，因为"abababab}"它小于其所有后缀。

如果你附加'$'，你会得到错误的答案，因为"ab$"< "abab$"< "ababab$"< "abababab$"。

于 2021-07-30T15:22:02.843 回答