11732 - strcmp() Anyone?

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

11732 - strcmp() Anyone?

Post by shakil » Sat Feb 13, 2010 7:43 pm

Why WA!!! Please give me some sample input & output to make my code AC. Thanks.

Code: Select all

#include<stdio.h>
#include<string.h>

unsigned long long count,tc1;
long n,i,j,next,l,st,k,p,cas1,pp1;
long value[4000009],index1[4000009],brother[4000009];
char temp[1009];
char Ch[4000009];

int main()
{
 
while(1)   
{
scanf("%ld",&n);

if(n==0)
break;

Ch[0]='&';
value[0]=0;
index1[0]=-1;
brother[0]=-1;

next = 1;
count = 0;

for(i=0;i<n;i++)
{
scanf("%s",temp);
l = strlen(temp);

st = 0;

for(j=0;j<l;j++)
{
  tc1 = value[st];
  count = count + tc1;
  value[st]++;
  
  if(index1[st]!=-1)
  {
    pp1=index1[st];
    while(Ch[pp1]!=temp[j])
    {
         if(brother[pp1]!=-1)
         pp1=brother[pp1];
         else
         {
         brother[pp1]=next;
          value[next]=0;
          index1[next]=-1;
          brother[next]=-1;
          Ch[next]=temp[j];
          pp1=next;
          next++;
         }
    }
    st = pp1;                 
  }
  else
  {
  index1[st]=next;
  value[next]=0;
  index1[next]=-1;
  brother[next]=-1;
  Ch[next]=temp[j];
  st=next;
  next++;
  }
}

value[st]++;

}

cas1++;
printf("Case %ld: %llu\n",cas1,count);

}
return 0;    
}
SHAKIL

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11732 - “strcmp()” Anyone?

Post by brianfry713 » Fri Nov 18, 2011 2:48 am

I tested an input of 1000 identical strings of length 1000. The correct answer is (2*(len+1)*N*(N-1)/2)=999999000, your code returns 499500000.
Check input and AC output for thousands of problems on uDebug!

shakil_buet
New poster
Posts: 2
Joined: Sun May 06, 2012 7:41 pm

Re: 11732 - “strcmp()” Anyone?

Post by shakil_buet » Fri Oct 05, 2012 12:43 pm

i'm getting WA. please give me some critical input

Code: Select all


Got AC

Last edited by shakil_buet on Fri Oct 12, 2012 12:03 am, edited 3 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11732 - “strcmp()” Anyone?

Post by brianfry713 » Fri Oct 05, 2012 7:09 pm

This code won't compile, you're missing the definition of LL.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11732 - “strcmp()” Anyone?

Post by brianfry713 » Sun Oct 07, 2012 8:11 pm

Input:

Code: Select all

57
ezysdylljqinvhbynmarolqkmcjsmglndhfdpyyezhmtamorrdjpksojtwjdmgdlbzsmfyzjfnaldaerqyijktlibcltbjotc
znjdbzwibamjjnectkikuem
vhnjumwoupuchhrdcoqqtlvqjmioemeobnspxqsjhckdpguzusyqpaxalovhdutazehjxyvbzvtrls
adzjwconawdwakeusgtojrrvfokjgv
qcuiubrepnfwjplpfesypqajuclmhjapnlpotlzhilstxiwmpyzvfylviqpdcpipkysglhxkwkmc
uryhqizjpipxvtvpbafrrcuoucygxadtymewqagkolsxkslajivkkcmebdonshgsnouiuqtzbso
yqaysywitrovhylkphryycadklcdrkncbbhesxysgqiuutjxlioclqnqhkvrxggcf
uahtcffpzsqxepgrqqmsfjpzzpeqmeaakijjbqknbkmhfhrgettxuwyqvurjtikyf
hggdikhnrjwozxzvyqcimhqbvkhcvmcwbfsnwmkgcwvlhdkdflbkrmakkltkuqvlxtqpa
kdxswqezemtympsoznotcajcvqbisypwilrvdxeyxzytvetgrcdabyovmzmqnnynunvekfaujvelrlrdhofxyqylneczqoyoh
chzfocdalgkqiwistnydvdstzt
brnaoqaysjsrktrpmlamgonzggcgpkobfcmtqqvxkquzqndqsomaysdnehyktocrhyzv
jjtbwcmobvbfdzbzbyyesqodmggzbuvtahqh
sxwjnocsvmphlwvlqzjylsmndwn
fjlegkzkmpwpnggufbdaepdecklbtppxvjshybmsscuxnaaoirobwyhevqjkjeijz
mlqclsrfxtgninqrwctiohnyxluvugiiiwtellrffjhfcmwomfoecoeaieiivnpcvmgrmtfljcbbfmajmregvvtx
bgtgungf
hzjaiepat
jdvcyqzjxypvpjyizqjudgkcavz
tcpdlyarkzongikuwgcdgbkxfvuoyoolyanliyfitkldbozhcmog
dnlnlbrgnofaiehovztmwadandicbeuxpzgloicfuowoplcikyayyputigg
jkprobeebosixkhpm
tfjedyegtszwqwivpmajbcliikoirhhzleziacsig
bgmjxazwmmbmnvloilbhqvzmlidtxakvzdyaohspbtrgchujejpazbmohv
amdmcnnscipjpoeegcinejrcnaqelmqeolmzxpfvb
ibpcbdrsavfuvchhfthfrxqxkmrpwtpzhnaxnmyndniikcrgnoadr
pyrybppwwarzeqrabmuqeh
flxeqjhepwphzoqnufjjnohywbvjzvtcldviwi
wcagqhjrmilakrshkkyothbzdptakukmkeyaprzbgecqfvcvuqzfbterntjxd
zcxgqvtzbgyqvewivyjssuydbalnielemwpjrqcgyrukcdnifkvrepktncirttswngybuhnuqxcvys
orhnmhtm
gbwffwwmnngcjreuivrndenlvyeoptujqnxbwrihugiyghvntenrr
zwcqnapjwhejveafavatrlhibpthzoebmlwlopdglbrfze
wpjyltiyfrtkatgmcwpdjqwvlfhbdorhhqpuzgjtvypcgnvljdpsyzaykfeyqzxwicopdkylgrumpolflh
ornorqomrbmjairpgrrvtclnqhjeljmmjqkvejqejcssmfuiyvrpuxd
iexpmtlfniqmlgrzhjuyflzyhcwbehatzydbnvyyrwwwkgbxvenvdvztkuxbjaa
qcbnqtpeeuwgrinrqjujhpwuckpfuyagkxvkzafgdbnxquiafpocjpfcmsupnphtqhg
jqfbloagblfkyoxmjdtbazjbsvokfrwbk
rlgukadtxoiguyyembskeemqqigewccpfdykpiptmovjjojfor
sijadtxdlbayhejoywutwoexeizmxffqznlpvsprfafnrynaechjlwmykqwpepmnjgajb
tfzjjgalldselqpuqxhidkgojvkxtijmubgqkjlpgdsvupxlujbspsifkjhzcmqismcwduitmuqhttzlwdzubqrhjslujndoinu
xevztpgmeydncepkildlmhdqyzjxxyrwqom
rbgspdmpagboyarijsruppbfkcwyrkzqfxkfnwvkbhwpxkjeqlteerotaodmdqbwvgdsqythjcmzfknclsxqpmpxm
fplpqhpmmezia
zgvjakoensuqggapaudujpejgdieepcxydfpxxpdqgddcl
yjxge
hrwsgefgribkioffxetghhufbjgnnvjviqdrjkdxsz
piewaxdpgtikxiripcgnvwjcwiidyvsjzugnwjqpfvsqptiavcbyaypgmhnvvswzbnnvufftgnfgtaigzybczgptjz
sl
zwgkwukiocujfkaanpyfwnadzixcczguiijy
lfolavnbbxwtpgjgaohlmkqzpqhxphdkmfhvnsibejszlkr
voycbavmexqgtzpgbmaqmwecqzbzqevlbvcwwkhctikekytmrifafwsiimfgqbbl
ihvnpjyrfqoocatgmdwtktjgsokczkeiwgpnldpnjnvlgxhdzgylv
nllftehdvoaesllxeowudchqkrmejbdwmrtkldnblrqbwptujhlumgjh
fvfsoltclvjdlzjawpgjijhyoaxoctyxogpsjmwjfotrbdpgamj
boddzjyrwibwydakziyvwbuxzgbozipggsjycyjbgpalguuqzh
sawsvtotnfegkjhmhkmzogudk
0
AC output Case 1: 1710
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11732 - strcmp() Anyone?

Post by Repon kumar Roy » Sun May 24, 2015 1:30 pm

I am using sorting The string lexicographically
My programs outputs correct for small input..

Code: Select all

//
//  main.cpp
//  11732 - "strcmp()" Anyone?
//
//  Created by Repon Macbook on 4/3/15.
//  Copyright (c) 2015 Repon Macbook. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				5005
#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 debug(x)              cout <<#x <<" -> " << x << endl;
#define EPS				1e-7
#define fred()                 freopen("in.txt","r",stdin);
#define fwrt()               freopen("in.txt","w",stdout);
/*---- 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 ****************************/





class SUF_ARA{
      
public:
      #define LG LMT
      char A[LMT][1005];
      
      struct entry {
            int nr[2], p;
            
      } L[LMT] , T[ LMT ];
      
      
      int P[LG][LMT], N, i, stp, cnt;
      int lcpAr[LMT];
      int CT[LMT];
      int PFA[LMT];
      int maxlen;
      
      int cmp(struct entry a, struct entry b)
      {
            if( a.nr[0] == b.nr[0] && b.nr[1] == a.nr[1]) return 0;
            return 1;
            
      }
      
      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(CT ,0, (iM + 1) * sizeof(int));
            for(int i = 0 ; i< len; i ++ ) {
                  CT[v[i].nr[index] + 1] ++;
            }
            
            PFA[0] = CT[0];
            for(int i = 1 ; i <= iM /* IM */ ; i ++ ) {
                  PFA[i] = CT[i] + PFA[i-1];
            }
            
            for (int i = len - 1; i >=0 ; i -- ) {
                  PFA[v[i].nr[index] + 1] --;
                  T[PFA[v[i].nr[index] + 1]] = v[i];
            }
            
            for(int i = 0 ;i <len; i ++ ) v[i] = T[i];
            
      }
      void buildSA()
      {
            
            //N = strlen(A); // N is global
            
            for(int i = 0 ; i < N ; i ++ ) P[0][i] = A[i][0];
            
            for (stp = 1, cnt = 1; cnt <= maxlen ; stp ++, cnt ++)
            {
                  for (i = 0; i < N; i ++)
                  {
                        L[i].nr[0] = P[stp - 1][i];
                        L[i].nr[1] = ( A[i][cnt] );
                        L[i].p = i;
                  }
                  countingSort(L , 1 , N);
                  countingSort(L , 0 , N );
                  
                  //sort(L, L + N , cmp);
                  P[stp][L[0].p] = 0;
                  int id = 1;
                  for (i = 1; i < N; i ++){
                        
                        int res = cmp (L[i], L[i-1]);
                        if(res) P[stp][L[i].p] = id ++;
                        else P[stp][L[i].p] = id ++;
                        //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;
                  }
                  //if(id == N ) break;
                  
            }
            L[N].p = N;
      }
      
      int lcp(int x, int y)
      {
            
            int ret = 0;
            int i;
            for(   i = 0 ; A[x][i] || A[y][i] ; i++ ) {
                  if( A[x][i] != A[y][i]) return 2 * ret + 1;
                  ret ++;
            }
            
           return 2 * (ret + 1) ;
           // else return  2* ret + 1;
        
      }
      
      void buildLCP()
      {
            for(int i = 0; i < N-1 ; i ++) {
                  lcpAr[i]  = lcp(L[i].p, L[i+1].p);
                  //debug(lcpAr[i]);
            }
      }
      
};

SUF_ARA sf;

int main()
{
	
	int n ,cs = 0;

	freopen("in.txt", "r", stdin);
      
      
	while (1) {
		sc(n);
            
		if(n==0) break;
          
            sf.maxlen = 0;
            for( int i = 0; i < n ; i ++) {
                  scanf("%s",sf.A[i]);
                  sf.maxlen = max( sf.maxlen , (int) strlen(sf.A[i]));
                  
            }
		sf.N = n;
		sf.buildSA();
            sf.buildLCP();
            
            
            
            ll ans = 0;
            int cnt = 0;
            for(int i = 0 ; i < n  ; i ++ ) {
                  int iM = inf ;
                  for (int j = i + 1 ; j < n ; j ++ ) {
                        iM = min(iM , sf.lcpAr[j-1]);
                        //debug(iM);
                        ans += iM;
                        
                        cnt ++;
                  }
            }
            
            
            printf("Case %d: %lld\n" , ++cs, ans);
            
	}
	return 0;
}


Post Reply

Return to “Volume 117 (11700-11799)”