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