902 - Password Search

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

Moderator: Board moderators

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Mon Dec 04, 2006 4:59 pm

sakhassan wrote:still no clue!!!!!!!!!! :oops: :( :( :( still RTE

ok , your "char hash[M][N]; " , if we increase the size of N to
1000000 , what will happen ?? :D

think about it , maybe you shoud find a better solution !
:D
studying @ ntu csie

xlspace
New poster
Posts: 2
Joined: Sat Dec 23, 2006 3:38 pm

I get TLE

Post by xlspace » Sat Dec 23, 2006 4:19 pm

Code: Select all

#include <string>
#include <map>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

#define TSIZE 13881
typedef vector<map<string ,int> > HashTable;

void hash(string & sub, int & key1)
{
   key1 = 0;
   int i;
   int t = 1;
   int len = min<int>(5,sub.size());
   t = 1;
   for(i=0;i<len;i++)
   {
       t = (i<<1);
       key1 += (((int)(sub[i])-97))<<t;

   }
   key1 = key1%TSIZE;
}

int insert(HashTable & HT, string & sub)
{
   int key1;
   hash(sub,key1);
   map<string ,int>::iterator pos;
   pos = HT[key1].find(sub);
   if(pos == HT[key1].end())
   {
       HT[key1][sub] = 1;
       return 1;
   }
   else
   {
       pos->second++;
       return pos->second;
   }
}

string search(int N, string & S)
{
   int i,k;
   string sub;
   int T = 0;
   int t;
   string ret;
   HashTable HT = HashTable(TSIZE+1);
   sub = S.substr(0,N);
   k = 0;
   for(i=1;i<S.length()-N+1;i++)
   {
       sub.erase(sub.begin());
       sub.append(1,S[i+N-1]);
       t = insert(HT,sub);
       if(T < t)
       {
           T = t;
           k = i;
       }
   }
   ret = S.substr(k,N);
   return ret;
}
int main()
{
    int N;
    string buffer;
    while(cin>>N>>buffer)
    {
        cout<<search(N,buffer)<<endl;
    }
}
I use hashtable, but can also not solve, get TLE

can anyone help me

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Dec 23, 2006 7:17 pm

The best cpu time of this problem is near 1sec, so I think it will be hard to avoid TLE using STL.

xlspace
New poster
Posts: 2
Joined: Sat Dec 23, 2006 3:38 pm

get AC

Post by xlspace » Sun Dec 24, 2006 3:31 am

I get AC now,
first I not use substr function in string
second , I use pair<unsigned int, unsigned int> to represent a string

Thanks

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: get AC

Post by DJWS » Wed Feb 07, 2007 10:26 am

rio wrote:The best cpu time of this problem is near 1sec, so I think it will be hard to avoid TLE using STL.
I modified xlspace's code and got AC in 3.787 sec. It's possible to get AC using STL. :)
xlspace wrote:I get AC now,
first I not use substr function in string
second , I use pair<unsigned int, unsigned int> to represent a string.
Actually, you can use 'long long' to represent a string instead. That makes things simplier. :wink:

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Re: get AC

Post by rio » Thu Feb 08, 2007 4:24 am

DJWS wrote:Actually, you can use 'long long' to represent a string instead. That makes things simplier.
Cool idea :D I'll try it.

MaVa
New poster
Posts: 6
Joined: Wed Oct 25, 2006 6:01 pm

Re: 902 Password Search

Post by MaVa » Sun Feb 18, 2007 8:58 pm

Don't give up, it is possible to solve this problem in Java!
Darko wrote:This is what I do (n - number given (<=10), slen - length of the string):
- read string into an array (O(n))
- sort pointers to substrings (O(n*slen*log(slen)) <- bad?
- go through list of pointers and find the longest repeating sequence (O(n*slen))
Maybe your runningtime is too slow?
Representing the substrings as longs will help, then a comparison of two substrings is 1 operation, not n.
My solution uses almost 3sec, if I were to multiply by n, I would get TLE.
O() notation is nice, but remember that the constant term is very important:
O(n*slen) might be larger than O(slen*log(slen)) in practice.

zwshen
New poster
Posts: 1
Joined: Mon Apr 16, 2007 7:46 pm

serveral times of WA

Post by zwshen » Mon Apr 16, 2007 7:58 pm

:cry:

I had improved my code to overcome the Time Limit Exceeded.
The improvement approaches are using "constant-time sub-string" and
"Customized Hash function instead STL map". The code can be judged
in 2 sec. However, I meet several times of WA.

I thought that the possible reason is the collision of Hash function.
Because I applied the joaat_hash approach and a prime number 99991 as the maximum size of hash table, is the prime number not as large as enough?

Thanks you and have a nice day.

Juan Gomez
New poster
Posts: 1
Joined: Tue Jun 19, 2007 6:20 pm

Post by Juan Gomez » Tue Jun 19, 2007 6:38 pm

I have implemented a TRIE to store the possible passwords and it runs on 3.754 secs. It's no too fast but I think the source of the problem is in the way I'm reading the input. Have a nice day.

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

Post by LithiumDex » Sat Jul 14, 2007 11:56 pm

I used hashing.. I tried TRIES, they would have been fast if I had been able to use fixed links and not get MLE.

Anyway tho, hashing is fast enough.. and if you get the right hashing function (i.e. one of the more sensible obvious ones), you can avoid key errors while using unsigned int's. Also... If you assume something very dangerous about the nature of the most likely randomly generated larger test case, you can half your time.
- Chris Adams

gaucho.andre
New poster
Posts: 3
Joined: Fri Aug 31, 2007 8:33 am

Post by gaucho.andre » Sat Sep 01, 2007 9:25 am

That' my code. The algorythim seems ok and it works fine on eclipse, but i still get Compile Error message. Does anybody have a clue about waht's wrong on this program? P.S. JAVA program:

Code: Select all

import java.io.IOException;
import java.util.StringTokenizer;

class Problem902 {
	
	static String testCase, codeLine,password;
	static StringTokenizer st;
	static short N, m, max;
	static char[] code, passwordVet;
	static String[] allPasswords;
	static short[] numPasswords;
	
	public static void main(String[]args){
		
		while(true){
			input();
			if(testCase == null)break;
			input(testCase);
			setArrays();
			
			for(short i = 0; i <= (code.length-N); i++){
				
				password = getPass(i);
				checkPass(password);
			}
			System.out.println(findPass());
	
		}
		
	}
	
	//Method to read from input, copied from problem100 sample solution
	static String ReadLn (int maxLg)
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null);
        return (new String (lin, 0, lg));
    }
	
	//Method to read a line from the input
	static void input(){
		testCase = ReadLn(255);
	}
	
	//Method to convert the line read from the other method into a number (N) and a string(codeLine)
	static void input(String linha){
		
		st = new StringTokenizer(linha);
		N = Short.parseShort(st.nextToken());
		codeLine = st.nextToken();
		
	}
	
	//Method to convert codeLine into a char Array and to create 3 other arrays
	static void setArrays(){
		
		code = codeLine.toCharArray();
		passwordVet = new char[N];						//stock a password to work with
		allPasswords = new String[(code.length-(N-1))]; //stock all passwords already reads
		numPasswords = new short[allPasswords.length];  //count how many times a certain password was read. it conects with allPasswords by using the same index (i.e. numpasswords[2] counts how many times the string in allPasswords[2] was read
	}
	
	//Method to get 3 chars in a row and convert to a String
	static String getPass(short i){
		
		for(short j = 0; j < N; j++, i++) passwordVet[j] = code[i];
		String pass = new String(passwordVet);
		return pass;
			
	}
	
	//Method to use a String and check if i has already been read
	static void checkPass(String pass){
		
		for(m = 0; m < allPasswords.length; m++){
			if(allPasswords[m] == null){
				allPasswords[m] = pass;
				numPasswords[m]++;
				break;
			}
			
			if(saoIguais(allPasswords[m], pass)){
				numPasswords[m]++;
				break;
			}
		}
	}
	
	//Method to seek allPasswords and numPasswords and return the most read password as answer for the test case
	static String findPass(){
		max = 0;
		for(short i = 0; i < numPasswords.length; i++){
			if(numPasswords[i] > max) max = numPasswords[i];
		}
		for(short i = 0; i < numPasswords.length; i++){
			if(numPasswords[i] == max) return allPasswords[i];
		}
		return "";
		
	}
	
	//Method to compare 2 Strings. P.S. Don't know why, but using "if(a == b)" didn't work
	static boolean saoIguais(String a, String b){
		char[] aa = a.toCharArray();
		char[] bb = b.toCharArray();
		
		for(short i = 0; i < aa.length; i++){
			if(aa[i] != bb[i])return false;
		}
		return true;
		
	}
}
That's the message i've received:

Code: Select all

Here are the compiler error messages:

05882640_24.java: In class `Main':
05882640_24.java: In method `main(java.lang.String[])':
05882640_24.java:21: Internal compiler error in `expand_expr', at expr.c:5844
So, does anybody can see which is the compile error on this code?

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

Post by kenneth » Thu Mar 20, 2008 4:08 pm

Hi Guys, I got my solution accepted with run time of 2.830 seconds so it's not extremely fast but it's not bad.

I can see that there are lots of ideas came up in the discussion but I solved this problem just by brute force using substring function and a map (I coded in C++).

Say for string "baababacb", you can use a map to count the number of occurance of each substring

baa 1
aab 1
aba 2
bab 1
bac 1
acb 1

After that, just find the max number of occurance which is 2 and the answer is aba. There is no special case, that is you will never have more than 1 substrings that could be the answer.

The complexity of the algorithm is O(n) as you only need to go thru the string once followed by going thru the map once. Hope this helps.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Mar 20, 2008 6:42 pm

kenneth wrote:The complexity of the algorithm is O(n) as you only need to go thru the string once followed by going thru the map once. Hope this helps.
but access map and insertion in map will cost O(logn), Sor your algorithm is not O(n) it is O(nlogn).

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

Post by kenneth » Fri Mar 21, 2008 4:11 am

emotional blind wrote:
kenneth wrote:The complexity of the algorithm is O(n) as you only need to go thru the string once followed by going thru the map once. Hope this helps.
but access map and insertion in map will cost O(logn), Sor your algorithm is not O(n) it is O(nlogn).
Thanks for pointing that out. But the STL has optimised that so it is much more efficient than you trying to build a binary tree yourself :D

Like I said it's not super fast but enough to run within 10 seconds.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Fri Mar 21, 2008 2:22 pm

hint: I solved it using O(n*k) algorithm.

Post Reply

Return to “Volume 9 (900-999)”