Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Solution using Z-function is O(n) but gives TLA | Anton | 1423. Басня о строке | 13 апр 2023 23:25 | 1 | Unexpected result: the solution using z-function is O(n) but gives TLA on the 8th test. The solution doesn't pass so I will leave the code with it here. I'm wondering if it really doesn't pass the 8th test because it is too slow though is O(n), or if there's just some kind of error in my algorithm. vi ZFunction(string &p, string &s) { int n = (int) p.size(); vector<int> z(n + 1); for (int i = 0, l = 0, r = 0; i < n; ++i) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && p[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z; } .... vector<int> z_func = ZFunction(s1, s2); vector<int> z_func2 = ZFunction(s2, s1); for (int i = 0; i < n; ++i) { if (z_func[i] == n - i && z_func2[n - i] == i) { cout << i; return; } } cout << "-1"; Edited by author 13.04.2023 23:25 Edited by author 13.04.2023 23:25 Edited by author 13.04.2023 23:27 | hint for WA#2 | Accepted | 1423. Басня о строке | 31 мар 2023 17:48 | 4 | such data: 3 aaa aaa the answer is 0 rather than 3 I mean, it works, but the statement says that "If the problem has several solutions, you may output any of them". Obviously, 3 is the correct answer as well. So I guess it's test/statement problem? | Hint (AC in 0.015 using KMP) | Hristo Nikolaev (B&W) | 1423. Басня о строке | 29 ноя 2022 21:39 | 1 | | hint | Anton | 1423. Басня о строке | 31 авг 2021 16:33 | 1 | hint Anton 31 авг 2021 16:33 | Hint For Test Case# 16 | Yuv | 1423. Басня о строке | 4 сен 2019 10:49 | 2 | Cannot break this case. Any hint? Ok I don't know what was the case# 16. But I have found some test cases: 9 abghxrfab rfabghxrf ans: -1 9 abghxabab ababghxab ans: 2 12 abcghxabcabc cabcghxabcab ans: 1 | No subject | Islam | 1423. Басня о строке | 17 окт 2018 09:57 | 1 | Please give me test 8!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | accepted | Mikhail | 1423. Басня о строке | 20 июн 2018 20:48 | 1 | //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; void Z_function (string &str, vi &z) { int n = str.size(); z.resize(n, 0); for (int i = 1, l = 0, r = 0; i < n; ++i) { if (i <= r) { z[i] = min(r - i + 1, z[i - l]); } while (i + z[i] < n && str[z[i]] == str[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = z[i] + i - 1; } } string str, s; vi z; int main() { int n; cin >> n >> str >> s; str += '$'; str += s; str += s; Z_function(str, z); fo(i, (int)z.size()) { if (z[i] == n) { cout << i - n - 1 << endl; re 0; } } cout << -1 << endl; re 0; } | Solution | Сонечка | 1423. Басня о строке | 14 апр 2018 23:59 | 1 | | WA11 | Didi (OSU11) | 1423. Басня о строке | 16 мар 2018 01:25 | 1 | WA11 Didi (OSU11) 16 мар 2018 01:25 Get me test, please! I use kmp. | Shortest solution | Dranik | 1423. Басня о строке | 9 ноя 2017 08:42 | 3 | int main() { int n; string s1, s2; cin >> n >> s1 >> s2; s1 += s1; int pos = (int) s1.find(s2); switch ( pos ) { case -1: cout << -1; break; case 0: cout << 0; break; default: cout << n-pos; } return 0; } Unfortunately, your solution has been rejudged. :) string.find() is too slow. Good luck! | WA8 with kmp!!! | YuFeng | 1423. Басня о строке | 11 июл 2017 23:44 | 2 | //#define LOCAL #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXN 250000+10 int N; char str1[MAXN], str2[MAXN]; char temp[MAXN*2]; int kmp(char* s, char* t, int pos); void get_next(char* t, int* next, int t_len); int main() { #ifdef LOCAL freopen("1423_String_Tale_2.in", "r", stdin); freopen("1423_String_Tale_2.out", "w", stdout); #endif scanf("%d", &N); scanf("%s%s", str1, str2);
int s1_len = strlen(str1); int s2_len = strlen(str2);
if(s1_len != s2_len){ printf("%d\n", -1); return 0; }
strcpy(temp, str1); strcat(temp, str1); int ans; ans = kmp(temp, str2, 0); if(ans != 0 && ans != -1) printf("%d\n", s1_len-ans); else printf("%d\n", ans); return 0; } int kmp(char* s, char* t, int pos) { int s_len = strlen(s); if(pos<0 || pos>s_len-1){ fprintf(stderr, "%s", "Error: invalid pos."); system("pause"); }
int t_len = strlen(t); int *next = (int*)malloc(sizeof(int) * t_len); get_next(t, next, t_len);
int i = pos; int j = 0; while(i<s_len && j<t_len){ if(j<0 || s[i]==t[j]){ i++; j++; } else j = next[j]; }
// free(next); if(j >= t_len) return i-t_len; else return -1; } void get_next(char* t, int* next, int t_len) { next[0] = -1; int j = 0; int k = -1; while(j < t_len){ if(k==-1 || t[j]==t[k]){ j++; k++; next[j] = k; } else k = next[k]; } } ############################################### Can anyone tell me WHY??? Edited by author 11.07.2017 19:31 Maybe you don't process characters with negative ASCII correctly. I don't know how standard string functions deal with negative ASCII. | WA8 Rabin–Karp and AC with KMP | Zura Isakadze [Tbilisi SU] | 1423. Басня о строке | 5 апр 2017 22:20 | 4 | any idea what could be my mistake? i'm using i=n; i< 2n; i++ h2=((mod + h2 - dn * a[i-n] % mod) * d % mod + a[i]) % mod; where d=256, dn=d^(n-1) mod=10^9+9 i had WA8 with hashes, i had maxn = 250100, but it must be doubled for algo and it passed with 500100 Boyer-Moor algorithm gets TL6 - it works slower than naive substrings search! AC with KMP | WA#4 | Giorgi | 1423. Басня о строке | 19 ноя 2016 03:00 | 1 | WA#4 Giorgi 19 ноя 2016 03:00 A can't understand what's the problem and why I don't pass it. Help me, please. | WA#8 test | Umidbek | 1423. Басня о строке | 14 сен 2016 15:43 | 1 | | Java AC 3rd place solution | esbybb | 1423. Басня о строке | 9 авг 2015 23:39 | 1 | //package timus; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.Reader; import java.util.StringTokenizer; public class p1423 { static char[] t; static char[] p; static int[] pi; static int N; public static void main(String[] args) throws FileNotFoundException { InputStream is = System.in; FastScanner sc = new FastScanner(new InputStreamReader(is)); N = sc.nextInt(); String tt = sc.next(); tt += tt; t = tt.toCharArray(); p = sc.next().toCharArray(); pi = new int[N]; System.out.println(KMPMatcher()); } static int KMPMatcher() { computePrefixFunction(); int equals = 0; for (int i = 0; i < N + N; i++) { while (equals > 0 && p[equals] != t[i]) equals = pi[equals - 1]; if (p[equals] == t[i]) equals++; if (equals == N) { if (i == N - 1) { return 0; } else { return N + N - (i + 1); } } } return -1; } static void computePrefixFunction() { int k = 0; for (int q = 1; q < N; q++) { while (k > 0 && p[k] != p[q]) k = pi[k - 1]; if (p[k] == p[q]) k++; pi[q] = k; } } static class FastScanner { BufferedReader br; StringTokenizer st; FastScanner(Reader in) { br = new BufferedReader(in); } String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } } } | Please help me! | Maksat "TheBiggestMax" Orazov | 1423. Басня о строке | 2 апр 2015 10:49 | 1 | # include <iostream> # include <fstream> # include <cmath> # include <vector> # include <algorithm> # include <math.h> # include <time.h> # include <string> # include <string.h> # include <map> # include <queue> # include <stack> using namespace std; const int MAXN = 1000000007;//, Maxn = 1000000009; long long n, a, san, num, dereje = 1, x; bool zero, one; string s, h; int main() { cin >> n >> s >> h;
a = n-1;
for (int i=0; i<n; i++) { san = (san + (dereje * (s[i]-'a'+1))) % MAXN; num = (num + (dereje * (h[i]-'a'+1))) % MAXN; dereje = (dereje * 27) % MAXN; }
if (san == num) {cout << 0 << '\n'; return 0;}
for (int i=0; i<n; i++) { san = (san * 27) % MAXN, san = (san - (((s[a]-'a'+1) * dereje) % MAXN)), san = (san + MAXN) % MAXN, san = (san + (s[a]-'a'+1)) % MAXN;
if (san == num) {cout << i+1 << '\n'; return 0;} a--; }
cout << -1 << '\n';
return 0; } WA 8.why? i used HASH! plz help me! | TLE on #8 | Shervin | 1423. Басня о строке | 11 фев 2015 09:24 | 1 | I'm using KMP I don't know why I get TLE? #include <iostream> int main(int argc, const char * argv[]) { long long int NumofChars; long long int finAns=-1;
scanf("%lld",&NumofChars);
char lettersS[2*NumofChars]; char lettersT[NumofChars]; char letter_tmp;
for (long long int i=0;i<NumofChars;i++) { scanf(" %c",&letter_tmp); lettersT[i]=letter_tmp; }
for (long long int i=0;i<NumofChars;i++) { scanf(" %c",&letter_tmp); lettersS[i]=letter_tmp; lettersS[i+NumofChars]=letter_tmp; }
long long int prefix[NumofChars]; prefix[0]=0; prefix[1]=0;
long long int pi=0; long long int pj=1;
while(pj<NumofChars-1) { if(lettersT[pi]==lettersT[pj]) { prefix[pj+1]=prefix[pj]+1; pi++; pj++;
} else {
pi=0; if(lettersT[pi]==lettersT[pj]) { prefix[pj+1]=1; pi++; pj++;
} else { prefix[pj+1]=0; pj++;
}
} }
finAns=-1;
long long int i=0; while(i<NumofChars) {
long long int Matchcount=0; long long int j_init=0; for (long long int j=j_init;j<NumofChars;j++) { if(lettersS[i+j]==lettersT[j]) { Matchcount++; } else { if(j-prefix[j]>0) { i=i+j-prefix[j]; j_init=prefix[j];
} else { i++; }
break; } }
if(Matchcount==NumofChars) { finAns=i;
break; } } std::cout<<finAns; return 0; } | WA 8 possibility | Kuros | 1423. Басня о строке | 26 дек 2014 02:35 | 1 | If you get WA 8 you might not be checking correctly for string equality once the hash goes through (false positive). | Помогите с решением | vot | 1423. Басня о строке | 7 ноя 2014 17:40 | 1 | Можете отправить работающую программу,если не сложно.Долго уже пытаюсь,не получается:( | Why Runtime error (access violation) ? | Kimbizin | 1423. Басня о строке | 4 июн 2014 22:18 | 1 | #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_READ 250000 #define MASIVE(a, b) (b *) malloc(sizeof(b *)*(a)) #define STRING(a) MASIVE((a), char); #define R_CONCAT(T,S,A) strcat(A, T); \ strcat(A, " "); \ strcat(A, S); \ int * Z_simple(char * str, int len) { int * z = MASIVE(len, int); for (int i = 1; i < len; i++) { int * val = z + i; *val = 0; for (int j = 0; i + j < len; j++) { if (str[i + j] != str[j]) { break; } (*val)++; } } return z; } int * Z(char * str, int len) { int * z = MASIVE(len, int); int l = 0, r = 0; for (int k = 1; k < len; k++) { if (k > r) { l = k; int pos = 0; while (k + pos < len && str[pos] == str[k + pos]) { pos++; } if (pos == 0) { r = l; z[k] = 0; } else { r = k + pos - 1; z[k] = pos; } } else { int m = k - l; int b = z[l] - m; if (z[m] < b) { z[k] = z[m]; } else { int pos1 = b; int pos2 = k + b; int pos = 0; while(pos2 + pos < len && str[pos1 + pos] == str[pos2+pos]) { pos ++; } if (pos != 0) { l = k; r = pos2 + pos - 1; z[k] = b + pos; } else { z[k] = b; } } } } return z; } int main() {
int n; int result = -1; scanf("%d", &n); char * T = STRING(n); char * S = STRING(n); scanf("%s%s", T, S); int len_N = 2*n + 1; char * N = STRING(len_N);
R_CONCAT(T,S,N); int * z = Z(N, len_N); z = z + (n + 1); for (int i = 0; i < n; i++) { if (z[i] == n - i) { int k = z[i]; int b = 0; for (int j = 0; j < i; j++) { if (T[k + j] != S[j]) { b = 1; break; } } if (b == 0) result = i; break; } } printf("%d", result); } |
|
|