Cheat Engine Forum Index Cheat Engine
The Official Site of Cheat Engine
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 


(Lua) How to find all instances of a string efficiently?

 
Post new topic   Reply to topic    Cheat Engine Forum Index -> Cheat Engine Lua Scripting
View previous topic :: View next topic  
Author Message
Dr.Disrespect
Grandmaster Cheater
Reputation: 3

Joined: 17 Feb 2016
Posts: 526
PostPosted: Sat Jun 17, 2017 2:38 pm    Post subject: (Lua) How to find all instances of a string efficiently? Reply with quote
What is the most efficient way to find all instances of a string in a string?

For example:
Code:

str = "hello world hello world hello world hello world hello world hello world hello world hello world"


How to find the positions of each "hello" effectively? Thanks.

Edit:
I tried "string.gmatch", but it can't return the index/position.
_________________
**************

A simple example is better then ten links. Very Happy
Back to top
View user's profile Send private message
ParkourPenguin
I post too much
Reputation: 140

Joined: 06 Jul 2014
Posts: 4289
PostPosted: Sat Jun 17, 2017 4:52 pm    Post subject: Reply with quote
If you want something simple, you could do this:
Code:
function basic_substr_iter(src, search)
  local i = 0
  return function()
    i = string.find(src, search, i+1, true)
    return i
  end
end

for i in basic_substr_iter('abbacababa','ab') do
  print(i)  -- prints index of occurrence
end

I don't know what algorithm string.find uses. If it's not fast enough for you, Google "string search algorithms".
_________________
I don't know where I'm going, but I'll figure it out when I get there.
Back to top
View user's profile Send private message
Dr.Disrespect
Grandmaster Cheater
Reputation: 3

Joined: 17 Feb 2016
Posts: 526
PostPosted: Sat Jun 17, 2017 5:34 pm    Post subject: Reply with quote
ParkourPenguin wrote:
If you want something simple, you could do this:
Code:
function basic_substr_iter(src, search)
  local i = 0
  return function()
    i = string.find(src, search, i+1, true)
    return i
  end
end

for i in basic_substr_iter('abbacababa','ab') do
  print(i)  -- prints index of occurrence
end

I don't know what algorithm string.find uses. If it's not fast enough for you, Google "string search algorithms".


Thanks, Penguin. Can you explain a little bit about the third and fourth parameter of the "string.find" function?
_________________
**************

A simple example is better then ten links. Very Happy
Back to top
View user's profile Send private message
ParkourPenguin
I post too much
Reputation: 140

Joined: 06 Jul 2014
Posts: 4289
PostPosted: Sat Jun 17, 2017 8:57 pm    Post subject: Reply with quote
Quote:
string.find (s, pattern [, init [, plain]])

Looks for the first match of pattern (see §6.4.1) in the string s. If it finds a match, then find returns the indices of s where this occurrence starts and ends; otherwise, it returns nil. A third, optional numeric argument init specifies where to start the search; its default value is 1 and can be negative. A value of true as a fourth, optional argument plain turns off the pattern matching facilities, so the function does a plain "find substring" operation, with no characters in pattern being considered magic. Note that if plain is given, then init must be given as well.
source
Basically, the third parameter is the index at which string.find should start looking (inclusive), and the fourth parameter is a boolean indicating if string.find shouldn't bother with magic characters in the pattern being searched for (e.g. %d, %s, %x, etc.). The only reason why I set that to true is because it would allow string.find to run faster. Whether it does or not I didn't test.
_________________
I don't know where I'm going, but I'll figure it out when I get there.
Back to top
View user's profile Send private message
Dr.Disrespect
Grandmaster Cheater
Reputation: 3

Joined: 17 Feb 2016
Posts: 526
PostPosted: Sun Jun 18, 2017 9:48 am    Post subject: Reply with quote
ParkourPenguin wrote:
Quote:
string.find (s, pattern [, init [, plain]])

Looks for the first match of pattern (see §6.4.1) in the string s. If it finds a match, then find returns the indices of s where this occurrence starts and ends; otherwise, it returns nil. A third, optional numeric argument init specifies where to start the search; its default value is 1 and can be negative. A value of true as a fourth, optional argument plain turns off the pattern matching facilities, so the function does a plain "find substring" operation, with no characters in pattern being considered magic. Note that if plain is given, then init must be given as well.
source
Basically, the third parameter is the index at which string.find should start looking (inclusive), and the fourth parameter is a boolean indicating if string.find shouldn't bother with magic characters in the pattern being searched for (e.g. %d, %s, %x, etc.). The only reason why I set that to true is because it would allow string.find to run faster. Whether it does or not I didn't test.


Thanks for the explanation, Penguin. Smile
_________________
**************

A simple example is better then ten links. Very Happy
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Cheat Engine Forum Index -> Cheat Engine Lua Scripting All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group

CE Wiki   IRC (#CEF)   Twitter
Third party websites