902 - Password Search

[SRX]

still no clue!!!!!!!!!! still RTE

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

think about it , maybe you shoud find a better solution !

[xlspace]

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

Code: Select all

[rio]

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

[xlspace]

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]

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.

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.

[rio]

Actually, you can use 'long long' to represent a string instead. That makes things simplier.

Cool idea I'll try it.

[MaVa]

Don't give up, it is possible to solve this problem in Java!

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]

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]

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]

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.

[gaucho.andre]

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]

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.

[emotional blind]

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]

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

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

[emotional blind]

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