Moderator: Board moderators

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am
emotional blind wrote:hint: I solved it using O(n*k) algorithm.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
kenneth wrote:
emotional blind wrote:hint: I solved it using O(n*k) algorithm.
try to implement a TRIE.

coze
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

This code gets Runtime error. Why?

Code: Select all

``````#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int N = 3000000;
char s[N];
int n_;

bool compare(const char* a, const char* b) {
return strncmp(a, b, n_) <= 0;
}

int main() {
int n;
while (2 == scanf("%d %s", &n, &s[0])) {
int len = strlen(s);
n_ = n;
assert(n < len);

vector<char*> v;
int m = len - n;
for (int i = 0; i <= m; i++)
v.push_back(s + i);

sort(v.begin(), v.end(), compare); // <-- !!!
}
}
``````

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

### Re: 902 - Password Search

Please help me. I am getting RE a huge number of time but I didn't find any fault in my code. I am reading all the post here

Code: Select all

``````#include<stdio.h>
#include<string>
#include<vector>
#include<iostream>
#include <stdlib.h>
#include "alloc.h"
using namespace std;

char str [ 10000000 ], *tok, s [ 10000000 ], password [ 10000000 ];

struct Trie
{
int word, prefix;
struct Trie* edges [ 27 ];
};

void init( struct Trie **node )
{
*node = (Trie*) malloc( sizeof( struct Trie ) );

(*node) -> word = 0;
(*node) -> prefix = 0;

for( int i = 0; i < 26; i ++)
{
(*node) -> edges [ i ] = NULL;
}
return;
}

bool is_empty( char *str )
{
return strlen( str ) <= 0;
}

void add_word( struct Trie **node , char *str, int i )
{
int k = str [ 0 ] - 'a';

if( is_empty( str ) )
{
(*node) -> word = (*node) -> word + 1;
return;
}
else
{
((*node) -> prefix) = ((*node) -> prefix) + 1;

if( ( *node ) -> edges [ k ] == NULL ) init( &(( *node ) -> edges [ k ] ));

add_word( &(*node) -> edges [ k ], &str [ i ], i ++ );
}
}
int count_words( struct Trie *node , char *str, int i )
{
int k = str [ 0 ] - 'a';
if( is_empty( str ) ) return node -> word;
else  if( node -> edges [ k ] == NULL ) return 0;
else return count_words( node -> edges [ k ], &str [ i ], i ++ );

}

int main()
{
//freopen("input.txt", "r", stdin);
int num, i, j, len, count, max;
Trie *t;

while( gets( str ) )
{
init( &t );
max = 0;

tok = strtok( str , " ");
sscanf(tok, "%d", &num);
tok = strtok( NULL , " ");
sscanf(tok, "%s", str);
//printf("%d %s\n", num, str);
len = strlen( str );
for( i = 0; i <= len - num; i ++ )
{
for( j = 0; j < num; j ++ )
{
s [ j ] = str [ i + j ];
}
s [ j ] = '\0';

count = count_words( t, s, 0 );

//printf("%s %d\n", s, count);

if( max < count)
{
max = count;
}
}

}
return 0;
}

``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 902 - Password Search

Perhaps, it has to do something with the fact that you don't free allocated memory?
You know, C++ doesn't have automatic garbage collection...

coze wrote:This code gets Runtime error. Why?
...
bool compare(const char* a, const char* b) {
return strncmp(a, b, n_) <= 0;
}
...
sort(v.begin(), v.end(), compare); // <-- !!!
RTFM:
http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

shankhs
New poster
Posts: 3
Joined: Tue May 20, 2008 4:10 am

### Re: 902 - Password Search

Why I am getting TLE?
I read in the previous posts that somebody got AC using map and substr , I have used only these things but still getting TLE!!!

Code: Select all

``````Code Removed after AC
``````

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 902 - Password Search

Can anyone post some input output?

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 902 - Password Search

Accepted.
A little mistake.
i<=(l-N) would be i<(l-N) and got ACC.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 902 - Password Search

I try to sloved this problem using Trie but it Wong answer.
Please give me some critical case

LegaNuno
New poster
Posts: 1
Joined: Mon May 02, 2011 7:08 pm

### getting RE on 902 - Password Search

So as you can see my probelm is that i have no ideia why this is getting me RE, i can compile it as normal and run it too
Your submission with number 8810000 for the problem 902 - Password Search has failed with verdict Runtime error.

This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.

Code: Select all

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

void string_procura(char str[],int n)
{
char **ptr=NULL;
int size=0,i=0,j=0,cont=0,total=0,pos=0;
size=(strlen(str)-n+1);
ptr=malloc(sizeof(char)*size);
for (i=0;i<size;i++)
{
ptr[i]=malloc(sizeof(char)*n);
strncpy(ptr[i],&str[i],n);
for (j=i;j<size;j++)
{
if (i!=j)
{
if (strncmp(ptr[i],&str[j],n)==0)
{
cont++;
if (cont>total)
{
total=cont;
pos=i;
}
}
}
}
}
if (total>0)
{
printf("%s",ptr[pos]);
for(i=0;i<size;i++)
free(ptr[i]);
free(ptr);
}
}

int main()
{
char str[100];
int n=0;
printf("Introduza o valor: ");
scanf("%d",&n);
printf("Introduza a frase :");
scanf("%s",str);
string_procura(str,n);
return 0;
}``````

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

### Re: 902 - Password Search

I got ac... my process is...
I find every sub string by using substr() function and use a map to count the frequency of those substring. just like this.

map<string,int>mp;

mp++;

then I found the max frequncy simply by linear search. But, by this process.....
input:
2 ababa
2 babab

both the ouput i got is ab. And I got ac. But I think the output of second case should be "ba".

I solved this problem using this approch long time ago..but I didn't submit my code consider this test cases. Today I submit and got AC.

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

### Re: 902 - Password Search

Why WA??????

Code: Select all

``````#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<cmath>
#include<string>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<utility>
#include<list>
#include<set>
#include<map>
using namespace std;
string s;

int main(){
string auxi;  int tam; map<string,int>mapa;
while(getline(cin,auxi)){
stringstream flujos(auxi);
flujos>>tam;  flujos>>s;  int l=s.size();
for(int i=0;i<l-tam+1;i++){
sol="";
sol=s.substr(i,tam);
mapa[sol]++;
}
map<string,int>::iterator it=mapa.begin();
while(it!=mapa.end()){
if( (*it).second > maximo){
maximo=(*it).second;
}
it++;
}

mapa.clear();
}
return 0;
}
``````
too i tried with ...

Code: Select all

``````for(int i=0;i<l-tam+1;i++){
sol="";
sol=s.substr(i,tam);
int as=++mapa[sol];
if( as > maximo){
maximo=as;
}
}

mapa.clear();

``````

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

### Re: 902 - Password Search

getting WA , plz help , code is at http://ideone.com/5P3YzZ

Thanks.

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

### Re: 902 - Password Search

gr81, don't read line by line on 902, you can change your loop to while(cin >> plen >> str) and get AC.
Check input and AC output for thousands of problems on uDebug!

MPC1984
New poster
Posts: 40
Joined: Mon Jul 01, 2013 9:24 pm
``````AC