I'm new in this community and with Python 3!
I'm trying to optimize this exercise:
We have
n
strings stored in a txt file. Inside the strings a secret word is hidden as a substring of consecutive characters.We know with certainty that the word repeats itself exactly once in each string but we don't know where.
Of the word we know the length
M
and we know that there are no other substrings of lengthM
which are repeated only once in all strings.We want to know for each string the position where the first character appears of the hidden word.
For example for the 3 strings with hidden word of length 3:
dogrtre sdfddoge bcb98xdoge42
the hidden word is 'dog' and the positions are in the order:
[0, 4, 6]
The information in the text file is organized as follows:
the first line contains the length of the hidden word (an integer).
then follow the character strings, each string occupies one or more consecutive lines of the file and is separated from the following string by an empty line.
Each line of the file ends with a newline.
This is my code now, it works, but I need to speed up the process of searching the hidden word...
The file.txt is:
3
dogrtre
sdfdd
oge
bc
b98xdo
ge42
As you can see the string in the file can stay on different lines. Can you help me?
#n=the lenght of the hidden word
#F=TextFile
#lista1=list of the possible hidden word of lenght n, the substring of the
#first string
#k=number of times that the word is in the file
#pos=list of position
def es1(ftesto):
def conta(F): #this function count the strings in the file
F.seek(0)
a=1
l=F.readline()
while l!='':
if l=='\n':
a+=1
l=F.readline()
return a
def crea_chiave(F): #this function read and split the first of the file
s='' #in substring of lenght n
l=F.readline()
while l!='\n':
s=s+l[:len(l)-1]
l=F.readline()
for i in range(0,len(s)-(n-1)):
if s[i:n+i] not in lista1: #it also control if there is
lista1.append(s[i:n+i]) #already the same substring in the
else: #string
lista1.remove(s[i:n+i]) #and in this case the function remove
#it from the list
def crea_lista(F,a,lista): #this function create the list
s=''
l=F.readline()
while l!='':
s=spezza(l,s,F)
if s not in lista: #if the string is already in the list,it goes
lista.append(s) #to the next one
else:
break
l=F.readline()
s=''
def spezza(l,s,F): #this function build the string from the file
while l!='\n' and l!='':
s=s+l[:len(l)-1]
l=F.readline()
return s
def controlla_parole(i,lista,k):#this function count how many times
for y in lista: #times the word repeat itself in each strings
if y.count(i)!=1: #if the word repeats itself 2 or 0 times
break #in the string it isn't the hidden word
else:
k+=1
return k
def trova_chiave(F,lista1,n): #this function find the hidden word
a=conta(open(ftesto,encoding='utf8'))
lista=[]
crea_lista(F,a,lista)
k=0
for i in lista1:
k=controlla_parole(i,lista,k)
if a==k: # if the number of hidden word repeats
break #itself in the file is the same of
k=0 #the number of strings in a file it is
return i #our hidden word
def controllo(F,l,chiave):# finally this func ,once we have the hidden
pos=[] #word,return the position of hiddenword in the
s='' #strings of file
while l!='':
while l!='\n' and l!='':
s=s+l[:len(l)-1]
l=F.readline()
pos.append(s.find(chiave))
s=''
l=F.readline()
return pos
F=open(ftesto,encoding='utf8')
n=int(F.readline())
F.seek(len(str(n))+1)
lista1=[]
crea_chiave(F)
F.seek(len(str(n))+1)
chiave=trova_chiave(F,lista1,n)
F.seek(len(str(n))+1)
return controllo(F,F.readline(),chiave)
With the given file the function does returns [0, 4, 6]
.
Can you help me to optimize and speed up this code? Thanks!!
dog
- each string containscbd
substring. How it should handle multiple common substrings with same length per each string? \$\endgroup\$crea_chiave()
may not work correctly if as[i:n+i]
is in the text more than 2 times (1st time it is added to lista1. 2nd time it is removed. 3rd time it is added again.). \$\endgroup\$