how find a char most use in a stirng ?

[mail.zhf]

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

 

[osmium]

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

Fill this array:

char cnt[26];

Then see which entry in the array has the largest value. There may be some
obnoxious, convoluted way to do it with the STL too.

 

[Zara]

:

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

Fill this array:

char cnt[26];

Then see which entry in the array has the largest value. There may be some
obnoxious, convoluted way to do it with the STL too.

Yes. Look at this beutiful piece of code:

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

typedef string::iterator s_iter;

// for counting chars
typedef map<char,size_t> charSet;
typedef charSet::iterator cs_iter;

// for ordering the results
typedef multimap<size_t,char,greater<size_t> > countSet;
typedef countSet::iterator cnt_iter;

// functor that counts chars
class countChar
{
private:
charSet& cs;
public:
countChar(charSet& chs):cs(chs) {}

void operator()(char c)
{
size_t count=1;
cs_iter csi=cs.find(c);
if (csi!=cs.end())
{
count=csi->second+1;
cs.erase(csi);
}
cs.insert(make_pair(c,count));
}
};

int main()
{
string str;
cout<<"Input your string: ";
cin>>str;

if (str.empty())
{
cout<<"This string is empty!!";
return -1;
}

charSet cs;
for_each (str.begin(),str.end(),countChar(cs));

countSet cnts;
for (cs_iter csi=cs.begin();csi!=cs.end();++csi)
{
cnts.insert(make_pair(csi->second,csi->first));
}

cout<<"The character(s) most used is/are:";

cnt_iter ci=cnts.begin();
size_t repetitions=ci->first;
for (;(ci!=cnts.end())&&(ci->first==repetitions);++ci)
{
cout<<' '<<ci->second;
}

}

Not much thought dedicated to it, I supose it shold be easy to obfuscate
it a lot more.

BTW, out is: s

 

[Gianni Mariani]

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

Your question is a little ambiguous.

If you are asking for the most frequently used character in a string,
the answer should be 's'.

What should be the output for this string:

"abc"

and this one

"cba"

and this one

"..."

and this one

""

and this one

"Aabbc"

?

 

[akarl]

if have two char use equality, out first.

???

 

[Dweia]

???

He's saying, if there are ultiple characters with equal frequency, e.g.
aabbcc, it returns the one which occurs first in the string, in the
above case, a.

 

[mail.zhf]

the method is best but i don't use stl, i want use c

:

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

Fill this array:

char cnt[26];

Then see which entry in the array has the largest value. There may be some
obnoxious, convoluted way to do it with the STL too.

Yes. Look at this beutiful piece of code:

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

typedef string::iterator s_iter;

// for counting chars
typedef map<char,size_t> charSet;
typedef charSet::iterator cs_iter;

// for ordering the results
typedef multimap<size_t,char,greater<size_t> > countSet;
typedef countSet::iterator cnt_iter;

// functor that counts chars
class countChar
{
private:
charSet& cs;
public:
countChar(charSet& chs):cs(chs) {}

void operator()(char c)
{
size_t count=1;
cs_iter csi=cs.find(c);
if (csi!=cs.end())
{
count=csi->second+1;
cs.erase(csi);
}
cs.insert(make_pair(c,count));
}
};

int main()
{
string str;
cout<<"Input your string: ";
cin>>str;

if (str.empty())
{
cout<<"This string is empty!!";
return -1;
}

charSet cs;
for_each (str.begin(),str.end(),countChar(cs));

countSet cnts;
for (cs_iter csi=cs.begin();csi!=cs.end();++csi)
{
cnts.insert(make_pair(csi->second,csi->first));
}

cout<<"The character(s) most used is/are:";

cnt_iter ci=cnts.begin();
size_t repetitions=ci->first;
for (;(ci!=cnts.end())&&(ci->first==repetitions);++ci)
{
cout<<' '<<ci->second;
}

}

Not much thought dedicated to it, I supose it shold be easy to obfuscate
it a lot more.

BTW, out is: s

 

[Zara]

the method is best but i don't use stl, i want use c

Then, why do you ask on comp.lang.c++? You should ask on comp.lang.c

 

[Gernot Frisch]

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

char MostUsed(const char* pC)
{
std::map<char, int> counts;
while(*pC!='\0')
{
counts[*pC] ++;
}
return *counts.front().first; // or back??
}

 

[msalters]

Gernot Frisch schreef:

char MostUsed(const char* pC)
{
std::map<char, int> counts;
while(*pC!='\0')
{
counts[*pC] ++;
}
return *counts.front().first; // or back??
}

How is counts['a'] initialized? Is it default-constructed or set to
int(0)?

HTH,
Michiel Salters

 

[Maxim Yegorushkin]

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

There are 3 f's and 4 s's in the string. Shouldn't it output s?

char most_used(char const* s)
{
unsigned freq[0x100] = {};
char c = 0;
for(; *s; ++s)
if(++freq[static_cast<unsigned>(*s)] >
freq[static_cast<unsigned>(c)])
c = *s;
return c;
}

If you change > to >= it will output the last found most used
charecter.

 

[Marc Mutz]

Gernot Frisch wrote:

char MostUsed(const char* pC)
{
std::map<char, int> counts;
while(*pC!='\0')
{
counts[*pC] ++;
}
return *counts.front().first; // or back??
}

<snip>

Yeah, right

Try
return counts.empty()
? '\0'
: min_element(counts.begin(),counts.end())->first;
instead.

Marc

 

[Karl Heinz Buchegger]

Gernot Frisch wrote:

char MostUsed(const char* pC)
{
std::map<char, int> counts;
while(*pC!='\0')
{
counts[*pC] ++;
}
return *counts.front().first; // or back??
}

<snip>

Yeah, right

Try
return counts.empty()
? '\0'
: min_element(counts.begin(),counts.end())->first;
instead.

I don't think this will work.
This will return the map element with the minimum *key*,
not with the minimum count.

You will need to use max_element (as the name MostUsed implies)
and have to use the predicate version of it, to search for the
maximum in the counts.

 

[akarl]

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

I'm feeling generous today, so here's a solution in C:

#define SIZE 256 /* number of values a char can assume */
#define OFFSET (SIZE / 2)

static int counts[SIZE]; /* counts[c + OFFSET] is the frequency of
char c */

/* most_common(s) returns the first character in the string s with
the highest frequency.

Precondition: s[0] != '\0'

Example: most_common("Alibaba") returns 'b'.
*/

char most_common(char s[])
{
int k;
char result;

assert(s[0] != '\0');
for (k = 0; k < SIZE; k++) { counts[k] = 0; }
k = 0;
while (s[k] != '\0') {
counts[(int) s[k] + OFFSET]++;
k++;
}
result = s[0];
k = 0;
while (s[k] != '\0') {
if (counts[(int) s[k] + OFFSET] > counts[(int) result + OFFSET]) {
result = (char) s[k];
}
k++;
}
return result;
}


August

 

[akarl]

#define SIZE 256 /* number of values a char can assume */
#define OFFSET (SIZE / 2)

static int counts[SIZE]; /* counts[c + OFFSET] is the frequency of
char c */

/* most_common(s) returns the first character in the string s with
the highest frequency.

Precondition: s[0] != '\0'

Example: most_common("Alibaba") returns 'b'.
*/

char most_common(char s[])
{
int k;
char result;

assert(s[0] != '\0');
for (k = 0; k < SIZE; k++) { counts[k] = 0; }
k = 0;
while (s[k] != '\0') {
counts[(int) s[k] + OFFSET]++;
k++;
}
result = s[0];
k = 0;
while (s[k] != '\0') {
if (counts[(int) s[k] + OFFSET] > counts[(int) result + OFFSET]) {
result = (char) s[k];

....and of course, this cast should be removed.

 

[Maxim Yegorushkin]

I'm feeling generous today, so here's a solution in C:

There is a number of problems in the solution:

1) The function is not reentrant.
2) It uses 2 loops instead of 1.
3) It operates on char[] rather than char const[] and does not handle
empty strings.

 

[akarl]

akarl wrote:

I'm feeling generous today, so here's a solution in C:

There is a number of problems in the solution:

1) The function is not reentrant.
2) It uses 2 loops instead of 1.
3) It operates on char[] rather than char const[] and does not handle
empty strings.

Thanks for your comments. Code reviewing is indispensable. Whether the
function should be thread-safe or not depends on the requirements (the
thread safe version is slightly slower). Can you think of any sensible
return value for an empty string?

Here is the modified version:

#include <assert.h>

#define SIZE 0x100 /* number of values a char can assume */
#define OFFSET (SIZE / 2)

/* most_common(s) returns the first character in the string s with the
highest frequency.

Precondition: s[0] != '\0'

Example: most_common("Alibaba") returns 'b'.
*/

char most_common(const char s[])
{
int counts[SIZE]; /* counts[c + OFFSET] is the frequency of char c */
int k;
char result;

assert(s[0] != '\0');
for (k = 0; k < SIZE; k++) { counts[k] = 0; }
result = s[0];
k = 0;
while (s[k] != '\0') {
counts[(int) s[k] + OFFSET]++;
if (counts[(int) s[k] + OFFSET] > counts[(int) result + OFFSET]) {
result = s[k];
}
k++;
}
return result;
}


August

 

[Maxim Yegorushkin]

akarl wrote:

I'm feeling generous today, so here's a solution in C:

There is a number of problems in the solution:

1) The function is not reentrant.
2) It uses 2 loops instead of 1.
3) It operates on char[] rather than char const[] and does not handle
empty strings.

Thanks for your comments. Code reviewing is indispensable. Whether the
function should be thread-safe or not depends on the requirements (the
thread safe version is slightly slower).

Mine is not.

Can you think of any sensible return value for an empty string?

An empty c-string contains a single character '\0', which is the most
used character in this case.

 

[akarl]

akarl wrote:



I'm feeling generous today, so here's a solution in C:


There is a number of problems in the solution:

1) The function is not reentrant.
2) It uses 2 loops instead of 1.
3) It operates on char[] rather than char const[] and does not handle
empty strings.

Thanks for your comments. Code reviewing is indispensable. Whether the
function should be thread-safe or not depends on the requirements (the
thread safe version is slightly slower).

The allocation of the array on the stack requires some extra instructions.

Mine is not.


An empty c-string contains a single character '\0', which is the most
used character in this case.

You may argue whether '\0' is really a *part* of the string or a string
delimiter, but as the behavior of strchr when given an empty string is
to return a pointer to the '\0' character I tend to agree with you.

Here is the final version:

#define SIZE 0x100 /* number of values a char can assume */
#define OFFSET (SIZE / 2)

/*
* most_common(s) returns the first character in the string s with the
* highest frequency.
*
* Example: most_common("Alibaba") returns 'b'.
*/

char most_common(const char s[])
{
int counts[SIZE]; /* counts[c + OFFSET] is the frequency of char c */
int k;
char result;

for (k = 0; k < SIZE; k++) { counts[k] = 0; }
result = s[0];
k = 0;
while (s[k] != '\0') {
counts[(int) s[k] + OFFSET]++;
if (counts[(int) s[k] + OFFSET] > counts[(int) result + OFFSET]) {
result = s[k];
}
k++;
}
return result;
}


August

 

[Maxim Yegorushkin]

Maxim Yegorushkin wrote:
[]

The allocation of the array on the stack requires some extra instructions.

Yes, this instruction on x86 is add esp, 0x100.