| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:用KMP,超时了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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator