10391 - Compound Words

[neowarez]

THis is my code for problem 10391

[pascal]
Program Problema_A(Input, Output);
Var
Conta, I, Temp, Conta2: LongInt;
Words: Array[1..120000] Of String;

Function Procurar(N: String): LongInt;
Var
I, J, A: Integer;
Begin
I:=1;
J:=Conta;
While (I<J) Do
Begin
A:=(I+J) Div 2;
If N<=Words[A] Then
J:=A
Else
I:=A+1;
End;
If N=Words Then
Procurar:=I
Else
Procurar:=0;
End;

Procedure GetData;
Var X, Y: LongInt;
Parte1, Parte2, Parte3 :String;
Begin
Repeat
Inc(Conta);
ReadLn(Input, Words[Conta]);
Until Eof(Input);
For I:=1 To Conta Do
Begin
Temp:=Length(Words);
Conta2:=I;
Repeat
Inc(Conta2);
X:=Pos(Words, Words[Conta2]);
If (X=1) Then
Begin
Parte1:=Words[Conta2];
Parte2:=Words;
Parte3:=Copy(Words[Conta2], Temp+1, Length(Words[Conta2]));
Y:=Procurar(Parte3);
If Not (Y=0) Then
WriteLn(Output, Parte1);
End;
Until Not (X=1);
End;
End;

BEGIN
GetData;
END.

[/pascal]

Why WA???

It result for the example.... and much more.

[little joey]

Read the previous thread on this problem. Your program doesn't deal correctly with Caesums input.

There are two errors (although they won't keep you from AC, I think):
- Conta is not initialised;
- Conta2 can get bigger than Conta and point beyond the last element of Words[].

Parta2 is assigned but never used, so get rid of it.

Your program structure is a mess. Variables are 'randomly' declared global or local, without any reason. The name GetData is misleading: besides reading the input, it processes it and produces the output. Either put the whole thing into the main program, or make three procedures: GetData, FindCompoundWords and WriteOutput, or something of the sort. Also don't mix Spanish(?) and English if you want other people to understand your code.

... I should realy contain myself by not being too patronising. Sorry for that, it's stronger than me...

[angga888]

HI, I'm also facing the same problem, always WA...
Please check my code and tell me my mistake, or give me some tricky input.

This is my code...

[pascal]--- Removed ---[/pascal]

Thanx for any help!

Regards,
angga888

[lord_burgos]

This is my program , I got Wa, why?

Code: Select all

Accepted

Hint

Code: Select all

Input
gera
geraaa
gerardo
rdo

Output
gerardo

[ayon]

what should be the result for the input?

ab
abab
abab

output:

abab
or,
abab
abab ?

[vinit_iiita]

Code: Select all

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    
    vector<string> v,r;
    string s;
    while (getline(cin,s))
    {
          v.push_back(s);
          }
         
        for (int i=0;i<v.size();i++)
          {     string d;
                 d=v[i];
          for (int t=0;t<v.size();t++)       
          for (int j=0;j<v.size();j++)
          if(d==v[t]+v[j])
          r.push_back(d);
          }
          sort(r.begin(),r.end());
          for (int k=0;k<r.size();k++)
          cout<<r[k]<<endl;
    
          return 0;
          }

     

i am getting compile error can any one help me plz..?[/b]

[mamun]

algorithm header file not included.

[vinit_iiita]

now i am getting TLE

[smilitude]

you have used a O(n^3) algorithm, worst case is huge (10^5)^3 = 10^15 .. its not supposed to work... i think an n^2logn is possible if you use binary search, that will be around 10^10, but i am not sure whether that will work.

stl and cin, cout will make your prog slower...

[Akter_Sust]

There is no same input.
for
ab
abab
input, output is
abab

[Ron]

Can someone tell me.. why i am getting TLE.....

Code: Select all

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(string s1,string s2){
	if(s2.size()<s1.size()){
		if(s2==s1.substr(0,s2.size()))	return true;
		return false;
	}
	return false;
}
int main(){
	long int l,i;
	string s;
	vector<string> v;
	vector<string>::iterator j,p;
	vector<int> y;
	while(cin>>s){
		v.push_back(s);		
		y.push_back(1);
	}
	for(i=0;i<v.size()-1;i++){
		j=search_n(v.begin()+i+1,v.end(),1,v[i],cmp);
		while(j<v.end()){
			if(y[j-v.begin()]==1){
				p=search_n(v.begin(),v.end(),1,v[j-v.begin()].substr(v[i].size()));
				if(p!=v.end()){
					cout<<*j<<endl;
					y[j-v.begin()]=0;
				}
			}
			j=search_n(j+1,v.end(),1,v[i],cmp);
		}
	}
	return 0;
}

[alamgir kabir]

I am getting TLE. please help me.
I use a string array to store all the string.
Then I take string and concate every string with it and binary search from the array to check whether
compound word is present or not. If present output it.
Why I am getting TLE.
My code is given bellow.

Code: Select all

cut after acc
thnks Jan. I have used Trie and got it accepted

Thanks everybody.

[Jan]

Use trie or hashing.

[MRH]

i sloved this problem but i can not remove WA.
i consider all given input & output but my program gave WA
please give me some critical input-output

thanks in advance

[parusa]

How many letters may stay in a word at most???????
It is not mentioned in this problem.