/* **************************************************************************** memory required: 13*N*integers where N is the length of input string ***************************************************************************/ #include #include #include // compilation options -- comment out the undesirable, while uncomment the // desirable // This option, if used, the input string with indexing is displayed #define _show_string // These options control what taks is to be performed, computing runs, or // distinct squares or maximal repetitions. // The optioins are listed in the order of precedence: e.g. if _runs and // _squares are both specified, runs will bo computed and not squares #define _runs //#define _squares //#define _maxreps // These options control the output // _show: the entities are nicely displayed as substrings of the input // string and the repating parts are distingusihed by alternating lower case // and the upper case. For this option, the string MUST consists of lower case // characters only. For distrinct squares the last occurrence is shown. // _output: the entities are ouput as 3-tuples for max reps and squares // (the last occurrence), or as 4-tuples for runs. There is no limitation // for the characters of the input string // _show takes precedence over _output //#define _show #define _output // if debugging, the debugging functions are in auxil.h, just uncomment // the next definition //#define _debug /* ********************************************************************** */ #ifdef _runs #undef _squares #undef _maxreps #endif #ifdef _squares #undef _maxreps #endif #ifdef _show #undef _output #endif typedef unsigned long ulong; ulong null; ulong N, N_1; #define setCMember(e,c) setCMember1(e,c,Gap,GNext,GPrev) void setCMember1(ulong e,ulong c,long* Gap,long* GNext,long* GPrev) { if (Gap[e] == null || Gap[e] < 0) if (c == null) Gap[e] = null; else Gap[e] = 0-1-c; else if (c == null) GNext[GPrev[Gap[e]]] = null; else GNext[GPrev[Gap[e]]] = 0-1-c; } #define getCMember(e) getCMember1(e,Gap,GNext,GPrev) ulong getCMember1(ulong e,long* Gap,long* GNext,long* GPrev) { if (Gap[e]==null) return null; else if (Gap[e] < 0) return 0-1-Gap[e]; else if (GNext[GPrev[Gap[e]]] == null) return null; else return 0-1-GNext[GPrev[Gap[e]]]; } #define CEnd(s) CPrev[CStart[s]] #define CSize(s) CNext[CPrev[CStart[s]]] #define GMember(p) \ ((getCMember(p)==null)?(null):((CStart[getCMember(p)]==p)?(null):(p-CPrev[p]))) #define F1(f) FStart[f] #define F2(f) \ ((F1(f)==null)?(null):((FPrev[F1(f)]==F1(f))?(null):((FNext[F1(f)])))) #define F3(f) \ ((F2(f)==null)?(null):((FPrev[F1(f)]==F2(f))?(null):((FNext[F2(f)])))) #define FBig(f) \ ((F2(f)==null)?(F1(f)):((CSize(F1(f))>CSize(F2(f)))?(F1(f)):(F2(f)))) #define CEmptyPop() CEmptyPop1(CEmpty,CEmptyTop,ScFirst,ScLast) inline ulong CEmptyPop1(ulong* CEmpty,ulong& CEmptyTop,ulong ScFirst, ulong ScLast) { if (CEmptyTop==null) return null; else return CEmpty[CEmptyTop++]; } #define CEmptyPush(a) CEmptyPush1(a,CEmpty,CEmptyTop,ScFirst) inline void CEmptyPush1(ulong a,ulong* CEmpty,ulong& CEmptyTop,ulong ScFirst) { CEmptyTop--; if (CEmptyTop <= ScFirst && ScFirst != null) { printf("CEmptyPush error\n"); getchar(); } CEmpty[CEmptyTop]=a; } #define FStartPop() FStartPop1(FStart,FStartTop) ulong FStartPop1(ulong* FStart,ulong& FStartTop) { ulong x; if (FStartTop==null) return null; else{ x = FStart[FStartTop]; if (FStartTop==0) FStartTop=null; else FStartTop--; return x; } } #define FStartPush(a) FStartPush1(a,FStart,FStartTop) inline void FStartPush1(ulong a,ulong* FStart,ulong& FStartTop) { if (FStartTop==null) FStart[FStartTop=0]=a; else FStart[++FStartTop]=a; } #define RStackPop() RStackPop1(RStack,RStackTop) inline ulong RStackPop1(ulong* RStack,ulong& RStackTop) { ulong x; if (RStackTop==null) return null; else{ x = RStack[RStackTop]; if (RStackTop==0) RStackTop=null; else RStackTop--; return x; } } #define RStackPush(a) RStackPush1(a,RStack,RStackTop) inline void RStackPush1(ulong a,ulong* RStack,ulong& RStackTop) { if (RStackTop==null) RStack[RStackTop=0]=a; else RStack[++RStackTop]=a; } #define SelIn(a) SelIn1(a,Sel,SelFirst,SelLast) inline void SelIn1(ulong a,ulong* Sel,ulong& SelFirst,ulong& SelLast) { if (SelLast==null) Sel[SelFirst=SelLast=0]=a; else Sel[++SelLast]=a; } #define SelOut() SelOut1(Sel,SelFirst,SelLast) inline ulong SelOut1(ulong* Sel,ulong& SelFirst,ulong& SelLast) { ulong x; if (SelFirst==null) return null; else{ x = Sel[SelFirst]; if (SelFirst==SelLast) SelFirst=SelLast=null; else SelFirst++; return x; } } #define ScIn(a) ScIn1(a,Sc,ScFirst,ScLast,CEmptyTop) void ScIn1(ulong a,ulong* Sc, ulong& ScFirst,ulong& ScLast,ulong CEmptyTop) { // note that we "loud" Sc in the wrong order, it is assumed that // after Sc is completely loaded, the conents are reversed if (ScFirst==null) Sc[ScFirst=ScLast=0] = a; else{ ScFirst++; Sc[ScFirst]=a; } if (ScFirst >= CEmptyTop) { printf("ScIn error\n"); getchar(); } } #define Reverse() Reverse1(Sc,ScFirst,ScLast) void Reverse1(ulong* Sc,ulong ScFirst,ulong ScLast) { ulong l, r, x; if (ScFirst == ScLast) return; l = ScLast; r = ScFirst; while(l < r) { x = Sc[l]; Sc[l] = Sc[r]; Sc[r] = x; l++; r--; } } #define ScOut() ScOut1(Sc,ScFirst,ScLast) ulong ScOut1(ulong* Sc,ulong& ScFirst, ulong& ScLast) { ulong x; if (ScFirst==null) return null; else if (ScFirst==ScLast) { x = Sc[ScFirst]; ScFirst=ScLast=null; return x; }else{ x = Sc[ScFirst]; ScFirst--; return x; } } #define FEnd(f) FPrev[FStart[f]] #define FMember(c) FMember1(c,FStart,FStartTop,FNext,FPrev) ulong& FMember1(ulong c,ulong* FStart,ulong FStartTop,ulong* FNext, ulong* FPrev) { if (FStartTop==null) return FStart[c]; else if (c <= FStartTop) return FNext[FPrev[FStart[c]]]; else return FStart[c]; } /* *************************************************************************** * uncomment if you need the auxiliary functions * ************************************************************************* */ #ifdef _debug #include "auxil.h" #endif // if the string is to be displayed, the auxiliary functions must be included #ifdef _show_string #include "auxil.h" #endif /* ************************************************************************** * class CROCH * ************************************************************************ */ class CROCH { private: ulong *block; ulong block_size; long number_of_classes; ulong* CStart; // 1 ulong* CNext; // 2 ulong* CPrev; // 3 ulong* CEmpty; // 4 ulong CEmptyTop; ulong* FStart; // 5 ulong FStartTop; ulong* FNext; // 6 ulong* FPrev; // 7 ulong* Refine; // 8 ulong* RStack; // 9 ulong RStackTop; ulong* Sel; // 10 ulong SelFirst, SelLast; ulong* Sc; ulong ScFirst, ScLast; long* Gap; // 11 long* GNext; // 12 long* GPrev; // 13 public: CROCH() { block=0; block_size=0; number_of_classes = 0; } // method Process ----------------------------------------------------------- // process the input string ulong Process(char* string,FILE* fp=stdout) { ulong L; bool done; ulong count=0; ulong n = strlen(string); init(n); #ifdef _show_string showString(string,N); #endif L = 1; done = Level_1(string); #ifdef _runs #ifdef _show count += traceRuns(string,L,fp,1); #else #ifdef _output count += traceRuns(0,L,fp,1); #else count += traceRuns(0,L,fp,0); #endif #endif #endif #ifdef _squares #ifdef _show count += traceSquares(string,L,fp,1); #else #ifdef _output count += traceSquares(0,L,fp,1); #else count += traceSquares(0,L,fp,0); #endif #endif #endif #ifdef _maxreps #ifdef _show count += traceMaxReps(string,L,fp,1); #else #ifdef _output count += traceMaxReps(0,L,fp,1); #else count += traceMaxReps(0,L,fp,0); #endif #endif #endif while(!done) { L++; done = Level(L); #ifdef _runs #ifdef _show count += traceRuns(string,L,fp,1); #else #ifdef _output count += traceRuns(0,L,fp,1); #else count += traceRuns(0,L,fp,0); #endif #endif #endif #ifdef _squares #ifdef _show count += traceSquares(string,L,fp,1); #else #ifdef _output count += traceSquares(0,L,fp,1); #else count += traceSquares(0,L,fp,0); #endif #endif #endif #ifdef _maxreps #ifdef _show count += traceMaxReps(string,L,fp,1); #else #ifdef _output count += traceMaxReps(0,L,fp,1); #else count += traceMaxReps(0,L,fp,0); #endif #endif #endif } return count; }//end Process // method init -------------------------------------------------------------- // allocate space and initilaize it void init(ulong n) { N=null=n; N_1=N-1; ulong size = 13*sizeof(ulong)*N; if (block_size < size) { if (block_size > 0) delete[] block; block_size=size; block = new ulong[block_size]; } for(ulong i=0; i < block_size; block[i++]=null); CStart = block; CNext = CStart+N; CPrev = CNext+N; CEmpty = CPrev+N; CEmptyTop = null; FStart = CEmpty+N; FStartTop = null; FNext = FStart+N; FPrev = FNext+N; Refine = FPrev+N; RStack = Refine+N; RStackTop = null; Sel = RStack+N; SelFirst = SelLast = null; Sc = CEmpty; ScFirst = ScLast = null; Gap = (long*) Sel+N; GNext = Gap+N; GPrev = GNext+N; // all classes are empty for(ulong i=N_1; ; i--) { CEmptyPush(i); if (i == 0) break; } number_of_classes = 0; }//end init /* ************************************************************************ * family handling methods * ***************************************************************************/ // method startFamily ------------------------------------------------------ ulong startFamily(ulong c) { ulong f; if (FStartTop == null) // save FMember value f = FStart[FStartTop = 0]; else f = FStart[++FStartTop]; FStart[FStartTop] = c; FNext[c] = f; // restore FMember FPrev[c] = c; // set FEnd return FStartTop; }//end startFamily // method addToFamily ------------------------------------------------------- // add class c to family f, always as a second element void addToFamily(ulong c,ulong f) { ulong f1, f2, f3; // if size of c > size of F2(f), we make c F2(f) // otherwise we make c F3(f) FMember(c) = f; if (FPrev[FStart[f]] == FStart[f]) { // singleton family, so c will become F2(f) f1 = FMember(f); // save FMember FNext[FStart[f]] = c; FPrev[c] = FStart[f]; FEnd(f) = c; // set FEnd FMember(f) = f1; // restore FMember }else{ if (CSize(c) > CSize(F2(f))) { // c will become F2(f) and F2(f) will become F3(f) f1 = F2(f); // save F2 f2 = FPrev[FStart[f]]; // save end f3 = FMember(f); // save FMember FNext[F1(f)] = c; FNext[c] = f1; if (f1 != null) FPrev[f1] = c; FPrev[c] = F1(f); FEnd(f) = f2; // reset end FMember(f) = f3; // restore FMember }else{ // c will become F3(f) f1 = F3(f); // save F3 if (FEnd(f)==F2(f)) // determine and save end f2 = c; else f2 = FEnd(f); f3 = FMember(f); // save FMember FNext[F2(f)] = c; FNext[c] = f1; if (f1 != null) FPrev[f1] = c; FPrev[c] = F2(f); FEnd(f) = f2; // reset end FMember(f) = f3; // restore FMember } } }//end addToFamily /* ************************************************************************ * class handling methods * ***************************************************************************/ // method startNewClass ------------------------------------------------------ // element e is put to a new class as a part of family f ulong startNewClass(ulong e,ulong f) { ulong c = CEmptyPop(); // take first available empty class CStart[c] = e; CPrev[e] = e; // set CEnd() CNext[e] = 1; // set CSize() setCMember(e,c); if (f != null) addToFamily(c,f); return c; }//end startNewClass // method addToNewClass ------------------------------------------------------ // element e is added to a new class c void addToNewClass(ulong e, ulong c, ulong f) { ulong l, r, f1, f2; ulong xend, xsize; // since the original parent mught have vanished, it is possible // that c == F1(f), in which case we leave it in place xend = CEnd(c); xsize = CSize(c)+1; if (F1(f) != c) { if (F2(f) != c) { if (xsize > CSize(F2(f))) { // must move c to be F2(f) f1 = FEnd(f); // save new FEnd if (f1 == c) f1 = FPrev[c]; f2 = FMember(f); // save FMember if (c == FStart[f]) l = null; else l = FPrev[c]; // save left neighbour if (c == FEnd(f)) r = null; else r = FNext[c]; // save right neighbour FNext[c]=FPrev[c]=null; // unlink c if (l != null) FNext[l] = r; // mend the hole if (r != null) FPrev[r] = l; // mend the hole l = F2(f); FNext[F1(f)] = c; FNext[c] = l; if (l != null) FPrev[l] = c; FPrev[c] = F1(f); FEnd(f) = f1; // restore FEnd FMember(f) = f2; // restore FMember } } } CNext[xend] = e; CPrev[e] = xend; CEnd(c) = e; // set CEnd() CSize(c) = xsize; // set CSize() setCMember(e,c); // now we have to add it to Gap insertGap(e,e-CPrev[e]); }//end addToNewClass // method removeFromClass -------------------------------------------------- // element e is removed from an existing class void removeFromClass(ulong e) { ulong e1, e2, c, f, f1, f2, f3, right, rgap, egap; ulong cend, csize; ulong gend; long cmember; c = getCMember(e); cend = CEnd(c); csize = CSize(c); if (e == cend) right = null; else{ right = CNext[e]; rgap = right-CPrev[right]; } if (e == CStart[c]) egap = null; else egap = e-CPrev[e]; setCMember(e,null); // removing e from class c csize--; // class c shrinks if (csize == 0) { // class vanishes, must be removed from family, since // it shrinks, it must be the first in the family f = FMember(c); if (f != null) { if (c != F1(f)) { printf("removeFromClass error\n"); exit(1); } f1 = F2(f); // save second guy in family f2 = FEnd(f); // save FEnd f3 = FMember(f); // save FMember FStart[f] = f1; FNext[c]=FPrev[c]=null; FEnd(f) = f2; // restore FEnd FMember(f) = f3; // restore FMember FMember(c) = null; } CNext[CStart[c]] = CPrev[CStart[c]] = null; setCMember(CStart[c],null); // this sets CEnd() and CSize() CStart[c] = null; CEmptyPush(c); number_of_classes--; }else{ if (CStart[c] == e) { // removing first element in the class CStart[c] = CNext[e]; setCMember(e,null); CEnd(c) = cend; CSize(c) = csize; CPrev[e] = CNext[e] = null; }else if (CEnd(c) == e) { // removing last element setCMember(e,null); CEnd(c) = CPrev[cend]; CSize(c) = csize; CPrev[e] = CNext[e] = null; }else{ // removing middle element setCMember(e,null); e1 = CPrev[e]; e2 = CNext[e]; CNext[e1] = e2; CPrev[e2] = e1; // CEnd(c) = cend; CSize(c) = csize; CNext[e] = CPrev[e] = null; } } // now we have to remove e it from Gap, if it is there if (egap != null) { if (Gap[egap] == e) { // e is the first in Gap if (GPrev[e] == e) { // the list is {e} cmember = GNext[e]; // save CMember value GNext[e] = GPrev[e] = null; Gap[egap] = cmember; }else{ gend = GPrev[Gap[egap]]; cmember = GNext[gend]; Gap[egap] = GNext[e]; GNext[e] = GPrev[e] = null; GPrev[Gap[egap]] = gend; GNext[gend] = cmember; } }else if (GPrev[Gap[egap]] == e) { // e is the last in Gap gend = GPrev[e]; // e has previous, otherwise e would be the first as well cmember = GNext[e]; GPrev[Gap[egap]] = gend; GNext[gend] = cmember; GNext[e] = GPrev[e] = null; }else{ // e is in the middle of Gap GNext[GPrev[e]] = GNext[e]; GPrev[GNext[e]] = GPrev[e]; GNext[e] = GPrev[e] = null; } } // now we have to update gap for the right neighbour if (right != null) { if (rgap != null) removeGap(right,rgap); if ((rgap = GMember(right)) != null) { insertGap(right,rgap); } } }//end RemoveFromClas /* ************************************************************************ * snapshot handling methods * ***************************************************************************/ // method createSnapshot ---------------------------------------------------- bool createSnapshot(ulong L) { // Create snapshot from curr. level for level L // parent-seed new families ulong f, c, c1, big, e, s; ulong maxd, x; // at this point RStack is not needed, we use it to seed new families RStackTop = null; for(f = 0; f <= FStartTop; f++) { // traverse all families // nullify the links, also delete all FMemebrs[c] for c <= FStartTops FNext[FPrev[FStart[f]]] = null; FPrev[FStart[f]] = null; c = FStart[f]; if (FNext[c] == null) { // *** singleton family, so no need to do snapshot if (CSize(c) == 1) { // ** singleton family of a singleton class // this does not go to the snapshot, so can push it onto CEmpty CPrev[CStart[c]] = CNext[CStart[c]] = null; setCMember(CStart[c],null); // this sets CEnd() and CSize() CStart[c] = null; CEmptyPush(c); if (c > FStartTop) FMember(c) = null; }else{ // ** singleton family of a thick class RStackPush(c); // make seed if (c > FStartTop) FMember(c) = null; } }else{ // *** thick family, so must choose small ones // determine big class big = FBig(f); while(c != null) { // traverse the family if (CSize(c) == 1) { // singleton class if (c == big) { // this does not go into snapshot, so we can push it onto CEmpty CPrev[CStart[c]] = CNext[CStart[c]] = null; setCMember(CStart[c],null); CStart[c] = null; // remove the class CEmptyPush(c); // do not put in snapshot as it is big }else{ SelIn(CStart[c]); // put in snapshot ScIn(CStart[c]); } }else{ // thick class RStackPush(c); // make seed if (c != big) { // put in snapshot for(e = CStart[c]; ; e = CNext[e]) { SelIn(e); if (e == CEnd(c)) break; } ScIn(e); } } c1 = FNext[c]; FNext[c] = FPrev[c] = null; // remove from family if (c > FStartTop) FMember(c) = null; c = c1; }//endwhile }// end of singleton / thick family FStart[f] = null; // remove family }//endfor // now we have to reverse Sc Reverse(); // at this point, FStart[], FNext[] and FPrev[] ought to be empty FStartTop = null; // now all seeds are in RStack if (RStackTop == null) return true; // to indicate done // seed the families and decide if we need to continue; maxd = 0; while((c = RStackPop()) != null) { if ((x = CEnd(c) - CStart[c]) > maxd) maxd = x; if (FStartTop==null) FStartTop=0; else FStartTop++; s = FStart[FStartTop]; // save FMember[FStartTop] if any FStart[FStartTop] = c; FEnd(FStartTop) = c; // set FEnd FMember(FStartTop) = s; // restore FMember[FSTartTop] FMember(c) = FStartTop; // set FMemebr(c) } if (maxd < L) return true; // to indicate done return false; // to indicate not done }//end createSnapshott /* ************************************************************************ * Gap handling methods * ***************************************************************************/ // method insertGap --------------------------------------------------------- void insertGap(ulong p,ulong g) { // insert position p into Gap g long c, gend, cmember; if (Gap[g]==null) { // nothing stored in Gap[g] Gap[g]=p; GPrev[p]=p; // set GEnd GNext[p]=null; // set CMember }else if (Gap[g] < 0) { // Gap[g] contains CMember cmember = Gap[g]; // save CMember Gap[g] = p; // store p in Gap[g] GPrev[p] = p; // set GEnd GNext[p] = cmember; }else{ // Gap[g] contains gap gend = GPrev[Gap[g]]; c = Gap[g]; Gap[g] = p; GPrev[p] = gend; GNext[p] = c; GPrev[c] = p; } }//end insertGap // method removeGap -------------------------------------------------------- void removeGap(ulong p,ulong g) { // remove position p from Gap g long gend, cmember; if (Gap[g] == p) { // p is first if (GPrev[p] == p) { // gap is {p} cmember = GNext[p]; Gap[g]=cmember; GNext[p] = GPrev[p] = null; }else{ // gap is {p, ...} gend = GPrev[p]; cmember = GNext[gend]; Gap[g] = GNext[p]; GPrev[Gap[g]] = gend; GNext[gend] = cmember; GPrev[p] = GNext[p] = null; } }else if (GPrev[Gap[g]] == p) { // p is last gend = p; cmember = GNext[gend]; gend = GPrev[gend]; GPrev[Gap[g]] = gend; GNext[gend] = cmember; GPrev[p] = GNext[p] = null; }else{ // p in the middle GNext[GPrev[p]]=GNext[p]; GPrev[GNext[p]]=GPrev[p]; GNext[p]=GPrev[p]=null; } }//end removeGap /* ********************************************************************** * Refine handling methods * *************************************************************************/ // method cleanRefine --------------------------------------------------- void cleanRefine() { ulong c; while((c = RStackPop()) != null) Refine[c] = null; }//end cleanRefine /* ********************************************************************** * level handling methods * *************************************************************************/ // method Level_1 ---------------------------------------------------------- bool Level_1(char* string) { ulong i, j, c, c1, last, s, xend, xsize; ulong count; // count singletons on level 0 // on level 0 we do not list the implicit singleton class {N} // and for the snapshot we consider all classes small and {N} big for(i = 0; i < N; i++) { c = find(string[i]); // position i goes to class c if (CStart[c] == null) { // class c does not exist yet CStart[c] = i; CPrev[i] = i; // set CEnd() CNext[i] = 1; // set CStart() setCMember(i,c); c1 = CEmptyPop(); number_of_classes++; }else{ // class c already exists xend = CEnd(c); xsize = CSize(c); CNext[xend] = i; CPrev[i] = xend; xend = i; CNext[xend] = xsize+1; // set CSize() CPrev[CStart[c]] = xend; // set CEnd() setCMember(i,c); insertGap(i,i-CPrev[i]); } } //clean up Sel[0]=null; // was used by find() for(i = 0; i < N; i++) // were used by find FStart[i]=FNext[i]=FPrev[i]=null; // create a snapshot of small classes, all classes are small // and seed families and count singletons count = 0; for(i = 0; i < N; i++) { if (CStart[i] == null) continue; last = j = CStart[i]; for(j = CStart[i]; j != CEnd(i); j = CNext[j]) SelIn(j); SelIn(j); ScIn(j); if (CSize(i) == 1) { // singleton class cannot be removed, no room in Sc count++; }else{ // make parent seed if (FStartTop==null) // save FMember and move FStartTop s = FStart[FStartTop=0]; else s = FStart[++FStartTop]; FStart[FStartTop] = i; FPrev[i] = i; // set FEnd FNext[i] = s; // restore FMember FMember(i) = FStartTop; } }//endfor // now we have to reverse Sc Reverse(); if (count == N) // all small classes were singletons, hence all done return true; return false; }//end Level_1 // method Level -------------------------------------------------------- // used to create levels 1 and up bool Level(ulong L) { ulong s, e, e1, c, d, f, ssize; bool done; ssize = 0; while((s = ScOut()) != null) { if (s == 0) { // then the small class is {0} e = SelOut(); c = getCMember(e); // now we have room in CEmpty, so we can remove this class CPrev[e] = CNext[e] = null; setCMember(e,null); CStart[c] = null; CEmptyPush(c); number_of_classes--; continue; } while(true) { e = SelOut(); // element of the snapshot of a small class ssize++; if (e == 0) if (e == s) { if (ssize == 1) { // remove singleton small class // this makes room for CEmptyPush c = getCMember(s); if (c != null) { CNext[s] = CPrev[s] = null; setCMember(s,null); CStart[c] = null; CEmptyPush(c); number_of_classes--; } } cleanRefine(); ssize = 0; break; }else continue; e1 = e-1; c = getCMember(e1); // e1 is a member of class c if (c == null) { if (e == s) { if (ssize == 1) { // remove singleton small class c = getCMember(s); if (c != null) { CPrev[s] = CNext[s] = null; setCMember(s,null); CStart[c] = null; CEmptyPush(c); number_of_classes--; } } cleanRefine(); ssize = 0; break; }else continue; } f = FMember(c); // family seeded by c removeFromClass(e1); if (Refine[c] == null) { // no destination yet for class c RStackPush(c); Refine[c] = startNewClass(e1,f); number_of_classes++; }else{ // there is destination for class c d = Refine[c]; // d is the destination for c addToNewClass(e1,d,f); } if (e == s) { cleanRefine(); ssize = 0; break; } }//endwhile }//endwhile if (number_of_classes == 0) done = true; else done = createSnapshot(L+1); return done; }//end Level /* *********************************************************************** * maximal repetitions handling methods * **************************************************************************/ // method traceMaxRep ------------------------------------------------------- void traceMaxRep(ulong g,ulong p,ulong& first,ulong& last) { ulong q, c; first = last = p; RStackPush(p); Refine[p]=1; c = getCMember(first); // p being in Gap must have a prev and must be // a member of a class for(q = CPrev[first]; q != CStart[c]; q = CPrev[q]) { if ((first-q) == g) { first = q; if (GMember(first) != null) { RStackPush(first); Refine[first]=1; } }else break; }//endfor if ((first-q) == g) { first = q; if (GMember(first) != null) { RStackPush(first); Refine[first]=1; } } // so we have first if (last != CEnd(c)) { for(q = CNext[last]; q != CEnd(c); q = CNext[q]) { if ((q-last) == g) { last = q; if (GMember(last) != null) { RStackPush(last); Refine[last]=1; } }else break; }//endfor if ((q-last) == g) { last = q; if (GMember(last) != null) { RStackPush(last); Refine[last]=1; } } } // so we have position of the last occurrence of the generator last = last+g-1; // last position }//end traceMaxRep // method traceMaxReps ----------------------------------------------------- ulong traceMaxReps(char* string,ulong g,FILE* fp,bool show) { ulong p, first, last; ulong count = 0; if (Gap[g] == null || Gap[g] < 0) return 0; // we use RStack+Refine to indicate if we already visited it for(p = Gap[g]; ; p = GNext[p]) { if (Refine[p]!=null) if (p == GPrev[Gap[g]]) break; else continue; traceMaxRep(g,p,first,last); count++; if (show) { if (string==0) outputRun(first,g,(last-first+1)/g,0,fp); else showRun(string,first,g,(last-first+1)/g,0,fp); } if (p == GPrev[Gap[g]]) break; }//endfor cleanRefine(); return count; }//end traceMaxReps /* ********************************************************************** * runs handling methods * ************************************************************************ */ // method traceRuns ------------------------------------------------------ ulong traceRuns(char* string,ulong g,FILE* fp,bool show) { ulong p, first, last, fi, la, x, y, a, b; ulong count = 0; if (g > N/2) return 0; if (Gap[g] == null || Gap[g] < 0) return 0; // we use RStack+Refine to indicate if we already visited it for(p = Gap[g]; ; p = GNext[p]) { if (Refine[p]!= null) if (p == GPrev[Gap[g]]) break; else continue; // already done traceMaxRep(g,p,first,last); la = first+1; // so we have the first and the last occurrence of the max repeat // we have to check if we can shift left or right // first check left shift while(first > 0) { fi = first-1; if ((a = getCMember(fi)) == null) break; if ((b = getCMember(fi+g)) == null) break; if (a != b) break; traceMaxRep(g,fi+g,first,y); if (y > last) last = y; }//endwhile // then check right shift while(la < N) { if ((a = getCMember(la)) == null) break; if ((b = getCMember(la+g)) == null) break; if (a != b) break; if (Refine[la+g] != null) break; traceMaxRep(g,la,x,y); if (y > last) last = y; la++; }//endwhile count++; if (show) { if (string == 0) outputRun(first,g,(last-first+1)/g,(last-first+1)%g); else showRun(string,first,g,(last-first+1)/g,(last-first+1)%g); } #ifdef _debug BFrun(string,first,g,(last-first+1)/g,(last-first+1)%g); // check if the run is a real and complete run #endif if (p == GPrev[Gap[g]]) break; }//end for cleanRefine(); return count; }//end traceRuns // method outputRun ------------------------------------------------------ static void outputRun(ulong s,ulong p,ulong e,ulong t,FILE* fp=stdout) { fprintf(fp,"(%u,%u,%u,%u)\n",s,p,e,t); } // method showRun ------------------------------------------------------ static void showRun(char* string,ulong s,ulong p,ulong e,ulong t,FILE* fp=stdout) { ulong i, j, k; bool toggle = false; if (s != 0) return; if (2*p <= N/2) return; for(i = 0; i < s; i++) fputc('.',fp); for(j = 0; j < e; j++) { if (toggle) toggle=false; else toggle=true; for(k = 0; k < p; k++) { if (toggle) fputc(string[i++],fp); else fputc(string[i++]-'a'+'A',fp); }//endfor }//endfor if (toggle) toggle=false; else toggle=true; for(j = 0; j < t; j++) if (toggle) fputc(string[i++],fp); else fputc(string[i++]-'a'+'A',fp); for( ; i < N; i++) fputc('.',fp); fputc('\n',fp); }//end showRun /* ********************************************************************** * distinct squares handling methods * ************************************************************************ */ // method traceSquares ------------------------------------------------------ ulong traceSquares(char* string,ulong g,FILE* fp,bool show) { ulong p, c, top; ulong count = 0; if (g > N/2) return 0; if (Gap[g] == null || Gap[g] < 0) return 0; // we use RStack+Refine to remember the last position for each class for(p = Gap[g]; ; p = GNext[p]) { c = getCMember(p); if (Refine[c] == null) { RStackPush(c); Refine[c] = p; }else if (p > Refine[c]) Refine[c] = p; if (p == GPrev[Gap[g]]) break; }//endfor // now for each class we have the right most position top = RStackTop; // save top while((c = RStackPop()) != null) { count++; p = Refine[c]; if (show) if (string == 0) outputRun(CPrev[p],g,2,0); else showRun(string,CPrev[p],g,2,0); }//endwhile RStackTop = top; // restore top cleanRefine(); return count; }//end traceSquares /* *********************************************************************** * private methods * ************************************************************************* */ private: // method find ------------------------------------------------------------ // it is only used for creation of level 0. // FStart, FNext, FPrev are used to emulate a binary earch tree // to sort out the letters in the input string; SelQu[0] is used // as a static variable to remember the last node used ulong find(char c1) { ulong c = c1; if (Sel[0] == null) { Sel[0] = 0; // root FStart[0] = c; // root FNext[0]=FPrev[0] = null; // children return 0; } ulong n = 0; while(true) { if (c == FStart[n]) return n; // character c belongs to class n if (c < FStart[n]) { // go left if (FPrev[n] == null) { Sel[0]++; FPrev[n] = Sel[0]; FStart[Sel[0]]=c; FNext[Sel[0]]=FPrev[Sel[0]]=null; return Sel[0]; }else{ n = FPrev[n]; continue; } }else{ // go right if (FNext[n] == null) { Sel[0]++; FNext[n] = Sel[0]; FStart[Sel[0]] = c; FNext[Sel[0]] = FPrev[Sel[0]] = null; return Sel[0]; }else{ n = FNext[n]; continue; } } } return null; }//end find };//end class CROCH