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 such data: 3 aaa aaa the answer is 0 rather than 3 thnx a lot 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? 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 Please give me test 8!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! //#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; } Get me test, please! I use kmp. 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! //#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. 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 A can't understand what's the problem and why I don't pass it. Help me, please. //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()); } } } # 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! 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; } If you get WA 8 you might not be checking correctly for string equality once the hash goes through (false positive). Можете отправить работающую программу,если не сложно.Долго уже пытаюсь,не получается:( #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); } |
|