题解：UVA13257 License Plates

· · 题解

题目大意

在字符串 s 中找长度为三的不同子串个数（可以不连续）。

思路

暴力肯定是过不了的，考虑使用其他方法。

可以发现在 s 中，只包含 A 至 Z 的字符，考虑设计 3 个桶：

桶 a：若 x_i 为真，表示以 x_i 开头的子串已被统计

桶 b：若 y_{i,j} 为真，表示以 y_{i,j} 开头的子串已被统计

桶 c：若 z_{i,j,k} 为真，表示以 z_{i,j,k} 开头的子串已被统计

将上述桶放至循环内，可以大幅度优化时间复杂度，单组数据的时间复杂度约为 O(26^3)。

整体程序的时间复杂度为 O(T\times 26^3)。

关键代码

for(int i=0;i<s.size();i++)
{
    if(!a[s[i]-'A'])
    {
        a[s[i]-'A'] = 1;
        for(int j=i+1;j<s.size();j++) 
        {
            if (!b[s[i]-'A'][s[j]-'A'])
            {
                b[s[i]-'A'][s[j]-'A']=1;
                for(int k=j+1;k<s.size();k ++)
                {
                    if(!c[s[i]-'A'][s[j]-'A'][s[k]-'A'])
                    {
                        c[s[i]-'A'][s[j]-'A'][s[k]-'A']=1;
                        ans++;
                    }
                }
            }
        }           
    }
    cout<<ans<<endl;
}