Care to share your method?emotional blind wrote:hint: I solved it using O(n*k) algorithm.
902 - Password Search
Moderator: Board moderators
- emotional blind
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
Re: 902 Password Search
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); // <-- !!!
}
}
-
- 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
Thanks in advance
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';
add_word(&t, s, 0);
count = count_words( t, s, 0 );
//printf("%s %d\n", s, count);
if( max < count)
{
max = count;
strcpy( password, s);
}
}
printf("%s\n", password);
}
return 0;
}
Thanks in advance
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...
http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/StrictWeakOrdering.html
You know, C++ doesn't have automatic garbage collection...
RTFM: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); // <-- !!!
http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/StrictWeakOrdering.html
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!!!
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
Re: 902 - Password Search
Now i'm getting wrong answer.
Can anyone post some input output?
Can anyone post some input output?
Re: 902 - Password Search
Accepted.
A little mistake.
i<=(l-N) would be i<(l-N) and got ACC.
A little mistake.
i<=(l-N) would be i<(l-N) and got ACC.
Re: 902 - Password Search
I try to sloved this problem using Trie but it Wong answer.
Please give me some critical case
Thanks in advance
Please give me some critical case
Thanks in advance
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;
}
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;
string b=input.substr(address,length);
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.
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;
string b=input.substr(address,length);
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.
-
- New poster
- Posts: 18
- Joined: Sat Nov 20, 2010 7:44 pm
Re: 902 - Password Search
Why WA??????
too i tried with ...
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();
int maximo=0; string sol,cadena;
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;
cadena=(*it).first;
}
it++;
}
mapa.clear();
cout<<cadena<<endl;
}
return 0;
}
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;
cadena=sol;
}
}
mapa.clear();
cout<<cadena<<endl;
-
- 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!
Re: 902 - Password Search
Hi everybody!
Can anybody help me with this problem?
I don't know why I got RTE with this code:
Thanks in advance! 
Can anybody help me with this problem?
I don't know why I got RTE with this code:
Code: Select all
AC

Last edited by MPC1984 on Thu Sep 12, 2013 1:28 pm, edited 1 time in total.