Could anyone please give me more hint ?Adrian Kuegel wrote:It is possible to solve this problem in O(n).
I don't know how to do it in O(n)
Moderator: Board moderators
What do you mean "If there are matches more than one characters"? I cannot understand. Would mind give me a clear explanation, and give me the examples? Thanks.Hi javier lira,
You can try a case with aaaaa.....(repeat 10000 times)
or try a case with aaaaa...(5000 times)...bbbbb...(5000 times).
Remember that you don't need to scan from left to right for the start point with step 1 always.
If there are matches more than one characters, you can move to next start point with more steps.
Code: Select all
@ double the string -> str[] = "String""String"
@ i=0 j=1 k=0 len=str.length()
while(i<len && j<len)
# if(str[i+k] == str[j+k]) { k++; if(k==len) break; }
# if(str[i+k] > str[j+k]) { i=i+k+1; if(i<=j) i=j+1; k=0; }
# if(str[i+k] < str[j+k]) { j=j+k+1; if(j<=i) j=i+1; k=0; }
return Min(i,j)
Damn this is cool, I got AC with both Suffix Array and yours algorithm. My suffix array implementation was also O(n). But considering the coding complexity, suffix array is a shit when compared to this... Thanks for sharing!suneast wrote:hi , all :
I think I have a better O(N) solution using an Algorithm by "??(ZhouYuan)" called "?????(Minimum Expression)" in Chinese..![]()
A simple code using O(N)time above will solve the problem![]()
if U want to know more details about the algorithm, you can search the Internet using keyword "?? ?????" (in Chinese)
Hope I'm help to you all
Code: Select all
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LMT 400006
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define msg(x) cout<<x<<endl;
#define EPS 1e-7
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/*************************** END OF TEMPLATE ****************************/
#define LG 21
char A[LMT];
struct entry {
int nr[2], p;
} L[LMT] , T[ LMT ];
int P[LG][LMT], N, i, stp, cnt;
int counterAray[LMT];
int prefixArray[LMT];
int cmp(struct entry a, struct entry b)
{
return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
}
void countingSort (entry v[] , int index , int len )
{
int iM = -100;
for(int i = 0 ; i < len ; i ++ ){
iM = max(iM , v[i].nr[index] + 1);
}
memset(counterAray ,0, (iM + 1) * sizeof(int));
for(int i = 0 ; i< len; i ++ ) {
counterAray[v[i].nr[index] + 1] ++;
}
prefixArray[0] = counterAray[0];
for(int i = 1 ; i <= iM /* IM */ ; i ++ ) {
prefixArray[i] = counterAray[i] + prefixArray[i-1];
}
for (int i = len - 1; i >=0 ; i -- ) {
prefixArray[v[i].nr[index] + 1] --;
if( prefixArray[v[i].nr[index] + 1] < 0 ) {
printf("ARRAY LESS\n");
}
T[prefixArray[v[i].nr[index] + 1]] = v[i];
}
for(int i = 0 ;i <len; i ++ ) v[i] = T[i];
}
void buildSA()
{
for (N = strlen(A), i = 0; i < N; i ++)
P[0][i] = A[i] - 'a';
for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1)
{
for (i = 0; i < N; i ++)
{
L[i].nr[0] = P[stp - 1][i];
L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
L[i].p = i;
}
//countingSort(L , 1 , N);
//countingSort(L , 0 , N );
sort(L, L + N , cmp);
for (i = 0; i < N; i ++)
P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;
}
}
int lcp(int x, int y)
{
int k, ret = 0;
if (x == y) return N - x;
for (k = stp - 1; k >= 0 && x < N && y < N; k --){
if( k >= LG ) {
printf("LHSLHDD\n");
}
if (P[k][x] == P[k][y])
x += 1 << k, y += 1 << k, ret += 1 << k;
}
return ret;
}
int main()
{
int tc;
//freopen("in.txt", "r", stdin);
sc(tc);
while (tc -- ) {
scanf("%s",A);
strcat(A, A );
buildSA();
int ans = -1;
for(int i = 0; i < N -1 ; i ++ ) {
if(L[i].p < N/2 ) {
if(ans ==-1 ) ans = L[i].p;
if(lcp( ans , L[i + 1].p ) >= N / 2 ) {
if( ans > L[i+1]. p ) ans = L[i+1].p;
}
}
}
printf("%d\n", ans + 1 );
}
}