Brute force : Have 2 pointers one pointing to last character and other pointing to the first occurrence of last character. compare the chars at the corresponding positions and decrement both pointers. when the latter hits -1 increment the counter and reset it to its original value. if the comparison fails at any point reset the counter to 1 and find the position of next occurrence of the last char in the input string and repeat the process until both the index reduce to 0.
@Bharath you need to read a list of input strings terminated by "*" before processing the strings. testcase : aaabbbcccddaaabbbcccd On Tue, Dec 7, 2010 at 12:18 PM, bharath kannan <[email protected]>wrote: > I tried solving that prob..here's my code > > #include<iostream> > #include<string> > using namespace std; > main() > { > string s; > cin>>s; > while(1) > { > if(s.size()==1 && s[0]=='*') > break; > int length=1,curr=0,start=0,count=1; > for(int i=1;i<s.size();i++) > { > if(s[i]!=s[curr] && s[i]!=s[start]) > { > curr=0; > count=1; > length=i+1; > } > else if(s[i]!=s[start] && s[i]==s[curr]) > { > curr++; > } > else if(s[i]==s[start] && s[i]!=s[curr]) > { > length=i; > curr=0; > count=1; > i=i-1; > } > else if(s[i]==s[start] && s[i]==s[curr]) > { > if(i%length==0) > { > count++; > curr++; > } > else > curr++; > } > } > if(s[s.size()-1]==s[length-1]) > cout<<count<<"\n"; > else > cout<<"1\n"; > cin>>s; > } > } > > I am getting WA..anyone pls tel a testcase where the above code > fails..pls.. > > Thanks in advance.. > > > On Mon, Dec 6, 2010 at 5:44 PM, alexsolo <[email protected]> wrote: > >> http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
