Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:用KMP,超时了

Posted by moxin at 2018-06-21 19:36:19 on Problem 3349
In Reply To:Re:用KMP,超时了 Posted by:jonnyhsy at 2014-01-21 16:14:22
> 
> Hash + KMP 22XXms过了。。。。
>kmp可以通过
>附上代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 100005;
int str[MAXN][6];
int next[15];
void KMPGET(int word[])
{
    int len = 6;
    int k = -1;
    int j = 0;
    next[0] = -1;
    while (j < len - 1)
    {
        if (k == -1 || word[j] == word[k])
        {
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
}
int kmp(int word1[], int word2[])
{
    int i = 0;
    int j = 0;
    memset(next, 0, sizeof(next));
    KMPGET(word2);
    int len1 = 12;
    int len2 = 6;
    while (i < len1 && j < len2)
    {
        if (j == -1 || word1[i] == word2[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j == len2)
    {
        return i - j;
    }
    else
        return -1;
}
bool PD(int word1[], int word2[])
{
    int word3[15];
    int ans = 6;
    for (int i = ans - 1; i != -1; i--)
    {
        word3[ans - 1 - i] = word2[i];
    }
    int word4[20];
    int anss = 6;
    int j = 0;
    for (int i = 0; i < anss; i++)
    {
        word4[j++] = word1[i];
    }
    for (int i = 0; i < anss; i++)
    {
        word4[j++] = word1[i];
    }
    int flag;
    flag = kmp(word4, word2);
    if (flag != -1)
        return true;
    flag = kmp(word4, word3);
    //printf("%d\n",flag);
    if (flag != -1)
        return true;
    return false;
}
vector<int *> vec[99991];
int main()
{int n;
    bool flag = false;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = 0; j < 6; j++)
            scanf("%d", &str[i][j]), sum += str[i][j];
        sum = sum % 99991;
        if(vec[sum].size()!=0)
        {
        if (PD(str[i],vec[sum][0]))
            flag = true;
        else
            vec[sum].push_back(str[i]);
        }
        else
        {
            vec[sum].push_back(str[i]);
        }
    }
    if (flag)
        printf("Twin snowflakes found.\n");
    else
        printf("No two snowflakes are alike.\n");
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator