codeforces514c

4168 ワード

これは文字列ハッシュの問題で、まず彼に文字列ハッシュをあげてから、この問題はもう一つあります.この問題は、正しい文字列ハッシュの位置を見つけるには、1つの文字列ハッシュを変更してから、文字列ハッシュを検索する必要があります.次に現在位置の重み値を変更して、最後にsetの中にこのハッシュ値が辞書に問題を提起しているかどうかを見て、それから単語をテストして、もし1つが異なるならば辞書の中の単語を計算して、それから単語が辞書の中の単語であるかどうかをテストします
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int N = 655360;
const int M = 1e9 + 7;

LL f[N] = {1};
int n , m;
char s[N];
setst;

void init()// 
{
    for(int i = 1 ; i < N ; i++){
        f[i] = f[i - 1]*257%M;
    }
}

LL run(char *s)// 
{
    LL res = 0;
    int l = strlen(s);
    for(int i = 0 ; i < l ; i++){
        res = (res * 257 + s[i])%M;
    }
    return res;
}

int judge(char *s)// 
{
    LL h = run(s);
    int l = strlen(s);
    for(int i = 0 ; i < l ; i++){
        for(LL c = 'a' ; c <= 'c' ; c++){
            if(s[i] == c) continue;
            //if(st.find((((c-s[i])*f[l - i + 1] + h)%M + M) % M) != st.end()) return 1;
              if(st.find((((c-s[i])*f[l-i-1]+h)%M+M)%M)!=st.end()) return 1;// 
        }
    }
    return 0;
}
int main()
{
    init();
    scanf("%d %d", &n , &m);
    for(int i = 0 ; i < n ; i++)
        scanf("%s",s),st.insert(run(s));
    for(int i = 0 ; i < m ; i++)
        scanf("%s",s),puts(judge(s)?"YES":"NO");
    return 0;
}