51nod 1732 51nod婚姻介绍所 - dblank

51nod 1732 51nod婚姻介绍所

51nod除了在做OJ之外,还开展了很多副业。婚姻介绍所就是其中之一。

对于一个客户,我们可以使用一个字符串来描述该客户的特质。
假设现在我们有两个客户A和B。
A的特质字符串为:abcdefg
B的特质字符串为:abcxyz
则A和B的匹配度f(A, B)为A和B的最长公共前缀的长度,即len('abc') = 3
由于最近51nod经费紧张,所以夹克大老爷设计了一种压缩算法以节约内存。
所有用户的特质字符串都被存储在了一个长为n的字符串S中。(n <= 1000)用户的特质使用一个整数p表示,表示该用户的特质字符串为S[p...n - 1]。
现给定字符串S,与q次查询<ai, bi>(ai, bi分别为合法的用户特质整数)。请输出q次查询分别对应的客户匹配度。
Input
现给定字符串长度n,与字符串S。接下来是整数q,代表接下来有q次查询。
下面q行有两个整数ai, bi。代表查询特质为ai与bi的用户的匹配度。

1 <= n <= 1000
1 <= q <= 10^6

输入数据全部合法。
Output
每一行输出一个用户匹配度整数。
Input示例
12
loveornolove
5
3 7
0 0
9 1
3 1
9 5
Output示例
0
12
3
0
0
思路:直接把字符串倒转过来,然后dp[i][j]表示第i个和第j个的最长公共后缀,最后查询直接输出dp[n-u][n-v]就好了,O(n^2)预处理,O(1)查询。
#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<queue>  
#include<map>  
#include<vector>  
#include<cstring>  
#include<cmath>  
using namespace std;  
typedef long long ll;  
const int inf =0x3f3f3f3f;  
const double  pi = acos(-1.0);  
const int N = 1e3 + 10;  
int dp[N][N];  
char s[N],x[N];  
int main()  
{  
    int n, m;  
    scanf("%d", &n);  
    scanf("%s", s);  
    for(int i = 0; i<n; i++)  
    {  
        x[n-i-1] = s[i];  
    }  
    x[n] = '\0';  
    memset(dp, 0, sizeof(dp));  
    for(int i = 1; i<=n; i++)  
        for(int j = 1; j<=n; j++)  
        {  
            if(x[i-1] == x[j-1])  
            {  
                dp[i][j] = dp[i-1][j-1] + 1;  
            }  
            else dp[i][j] =0;  
        }  
        int u, v;  
        scanf("%d", &m);  
        while(m--)  
        {  
            scanf("%d%d", &u, &v);  
            printf("%d\n", dp[n-u][n-v]);  
        }  
        return 0;  
}  

 

相关文章

发表新评论