Cipher Message 3 - URAL 1996 - Virtual Judge (vjudge.net)

清疚 2022-09-07 14:34 9阅读 0赞

# [Cipher Message 3 - URAL 1996 - Virtual Judge (vjudge.net)][Cipher Message 3 - URAL 1996 - Virtual Judge _vjudge.net] #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<vector>
    #define db double
    #define reg register
    #define inl inline
    using namespace std;
    const int MAX_AB = 2e6 + 10;
    const int  MAX_FFT = 2e6 + 10;
    
    struct Virt {//负数的加减乘
        double x, y;
        Virt(double _x, double _y) { x = _x; y = _y; }
        Virt() {}
        Virt operator+(const Virt& t) { return { x + t.x,y + t.y }; }
        Virt operator-(const Virt& t) { return { x - t.x,y - t.y }; }
        Virt operator*(const Virt& t) { return { x * t.x - y * t.y,x * t.y + y * t.x }; }
    };
    Virt a[MAX_AB], b[MAX_AB];
    int lengtha, lengthb;
    int CK[MAX_AB];//则A串从第l位开始和B串匹配的代价是：
    struct  FFT//快速傅里叶变换
    {
        //存储
        double Pi = acos(-1.0);
        int l, rev[MAX_FFT];
        int limit;
        void init(int len)//len:为两个多项式乘积最高次幂为(degree(A)+degree(B))
        {
            limit = 1; l = 0;
            while (limit <= len) limit <<= 1, l++;
            for (int i = 0; i < limit; i++)
                rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
        }
        //后面的type表示要进行的变换是什么类型
        //1表示从系数变为点值
        //-1表示从点值变为系数
        void fast_fast_tle(Virt* A, int type)
        {
    
    
            for (int i = 0; i < limit; i++)
                if (i < rev[i]) swap(A[i], A[rev[i]]);//求出要迭代的序列
    
            for (int mid = 1; mid < limit; mid <<= 1)//待合并区间的中点
            {
                Virt Wn(cos(Pi / (db)mid), type * sin(Pi / (db)mid)); //单位根
                for (int R = mid << 1, j = 0; j < limit; j += R)//R是区间的右端点，j表示前已经到哪个位置了
                {
                    Virt w(1, 0);//幂
                    for (int k = 0; k < mid; k++, w = w * Wn)//枚举左半部分
                    {
                        Virt x = A[j + k], y = w * A[j + mid + k];//蝴蝶效应
                        A[j + k] = x + y;
                        A[j + mid + k] = x - y;
                    }
                }
            }
            // if (type == -1)for (int i = 0; i <= limit; i++)a[i].x = (long long)(a[i].x / limit + 0.5);
        }
    
    }fft;
    
    struct FFT_SOLVE_Fuzzy_matching//fft解决模糊匹配
    {
        string s1, s2;
        int n, m;
        int A[MAX_AB], B[MAX_AB];
        void fft_math(int x, int y)
        {
            for (int i = 0; i < fft.limit; i++)a[i] = b[i] = Virt(0, 0);
            
            for (int i = 0; i < n; i++)a[i].x = (A[i] == x);
            for (int i = 0; i < m; i++)b[i].x = (B[i]==y);
            
            fft.fast_fast_tle(a, 1); fft.fast_fast_tle(b, 1);
            for (int i = 0; i < fft.limit; i++)a[i] = a[i] * b[i];
            fft.fast_fast_tle(a, -1);
            for (int i = 0; i < fft.limit; i++)CK[i] += (int)(a[i].x / (double)fft.limit + 0.5);
             
        }
    }ac;
    int n, m;
    int s[MAX_AB], t[MAX_AB];//文本串s;模式串t;
    int ne[MAX_AB];
    int ans1, ans2;
    void get_ne()
    {
        ne[1] = 0;
        for (int i = 2, j = 0; i <= m; ++i) {
            while (j && t[i] != t[j + 1]) j = ne[j];
            if (t[i] == t[j + 1]) ++j;
            ne[i] = j;
        }
    }
    void kmp()
    {
        for (int i = 1, j = 0; i <= n; i++) {
            while (j && s[i] != t[j + 1])j = ne[j];
            if (s[i] == t[j + 1])
            {
                j++;
                if (j == m) {
                    if (ans1 > CK[i - 1]) {
                        ans1 = CK[i - 1];
                        ans2 = i - m + 1;
                    }
                    j = ne[j];
                }
            }
            else j = ne[j];
        }
    }
    void solve()
    {
        ans1 = ans2 = 1e9;
    
        for (int i = 0; i < n; i++)scanf("%d", &s[i]);
        for (int i = 0; i < m; i++)scanf("%d", &t[i]);
        fft.init(n + m);
        for (int i = 0; i <= fft.limit; i++)CK[i] = 0;
        ac.m = m; ac.n = n;
        for (int i = 0; i < n; i++)ac.A[i] = s[i] & 1;
        for (int i = 0; i < m; i++)ac.B[i] = t[m-1-i] & 1;
    
        ac.fft_math(0, 1); 
        
        ac.fft_math(1, 0);
    
        for (int i = n; i >= 1; i--)s[i] = s[i - 1] / 10;
        for (int i = m; i >= 1; i--)t[i] = t[i - 1] / 10;
    
        get_ne();
        kmp();
        if (ans1 == 1e9)puts("No");
        else {
            puts("Yes");
            printf("%d %d\n", ans1, ans2);
        }
    
    }
    
    int main()
    {
        while (~scanf("%d%d", &n, &m))solve();
        return 0;
    }

puts("Yes");
        printf("%d %d\n", ans1, ans2);
    }

int main()  
\{  
while (~scanf("%d%d", &n, &m))solve();  
return 0;  
\}

[Cipher Message 3 - URAL 1996 - Virtual Judge _vjudge.net]: https://vjudge.net/problem/URAL-1996
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]: /images/20220829/1732971bceb84b01b352c7c7481d66ba.png