Searching Substring in O(n) Time Complexity

Year : 2023 | Volume :01 | Issue : 01 | Page : 09-15
By

Abhay A. Nigadikar

Ilyas Shaikh

Sharada Patil

  1. Student, MCA (Master of Computer Application), Sinhgad Institute of Business Administration and Research, Danny Mehata Nagar, Kondhwa Budruk, Pune, Maharashtra, India
  2. Student, MCA (Master of Computer Application), Sinhgad Institute of Business Administration and Research, Danny Mehata Nagar, Kondhwa Budruk, Pune, Maharashtra, Inida
  3. Associate Professor, MCA (Master of Computer Application), Sinhgad Institute of Business Administration and Research, Danny Mehata Nagar, Kondhwa Budruk, Pune, Maharashtra, India

Abstract

This research paper presents a highly efficient algorithm for substring search within a given string, achieving a remarkable time complexity of O(n). The proposed algorithm utilizes a two-pointer approach to compare the given string with the targeted substring. By employing string concatenation, the algorithm dynamically constructs a resultant substring during the matching process. Upon completion of character matching, the algorithm compares the resultant substring with the targeted substring and returns the index position when a match is found. The main advantage of this algorithm is to search through the main string in linear time, outperforming alternative algorithms with higher time complexities such as O(n^2) or O(m*n). The practical applications of this algorithm are diverse, spanning text processing, pattern matching, and data analysis. The efficiency and effectiveness of the algorithm make it a valuable tool in various domains where rapid and accurate substring search is required. By introducing this algorithm, the research paper offers a substantial contribution to the field of string processing, addressing the need for efficient substring search techniques. The experimental evaluation of the algorithm demonstrates its superior performance compared to existing approaches, highlighting its potential for enhancing computational tasks that involve string manipulation. The presented algorithm opens new possibilities for improving efficiency and scalability in applications that rely on substring search operations, contributing to advancements in text mining, information retrieval, and data analytics.

Keywords: Substring search, algorithm, time complexity, linear time, O(n), two pointers, string concatenation

[This article belongs to International Journal of Algorithms Design and Analysis Review(ijadar)]

How to cite this article: Abhay A. Nigadikar, Ilyas Shaikh, Sharada Patil. Searching Substring in O(n) Time Complexity. International Journal of Algorithms Design and Analysis Review. 2023; 01(01):09-15.
How to cite this URL: Abhay A. Nigadikar, Ilyas Shaikh, Sharada Patil. Searching Substring in O(n) Time Complexity. International Journal of Algorithms Design and Analysis Review. 2023; 01(01):09-15. Available from: https://journals.stmjournals.com/ijadar/article=2023/view=112817

Browse Figures

References

  1. Aho AV, Corasick MJ. Fast pattern matching: an aid to bibliographic search. Commun ACM. 1975; 18 (6): 333–340.
  2. Damiani A, Masciocchi C, Lenkowicz J, Capocchiano ND, Boldrini L, Tagliaferri L, Cesario A, Sergi P, Marchetti A, Luraschi A, Patarnello S. Building an artificial intelligence laboratory based on real world data: the experience of Gemelli generator. Front Computer Sci. 2021; ;3: 768266.
  3. Rahim R, Ahmar AS, Ardyanti AP, Nofriansyah D. Visual approach of searching process using Boyer-Moore algorithm. J Phys Conf Series. 2017; 930 (1), 012001.
  4. Knuth DE, Morris JH Jr, Pratt VR. Fast pattern matching in strings. SIAM J Comput. 1977; 6 (2): 323–350.
  5. Namjoshi K, Narlikar G. Robust and fast pattern matching for intrusion detection. In: 2010 Proceedings IEEE INFOCOM, Sandiego, CA, USA, March 14–19, 2010. pp. 1– doi: 10.1109/INFCOM.2010.5462149.
  6. Gurung D, Chakraborty UK, Sharma P. Intelligent predictive string search algorithm. Procedia Computer Sci. 2016; 79: 161–
  7. Carmosino ML, Gao J, Impagliazzo R, Mihajlin I, Paturi R, Schneider S. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14–17, 2016. pp. 261–
  8. March SD, Jones AH, Campbell JC, Bank SR. Multistep staircase avalanche photodiodes with extremely low noise and deterministic amplification. Nat Photonics. 2021; 15 (6): 468–
  9. Hume A, Sunday D. Fast string searching. Softw Pract Experience. 1991; 21 (11): 1221–
  10. Hooimeijer P, Veanes M. An evaluation of automata algorithms for string analysis. In: Verification, Model Checking, and Abstract Interpretation: 12th International Conference, VMCAI 2011, Austin, TX, USA, January 23–25, 2011. Berlin, Germany: Springer; 2011. pp. 248–
Regular Issue Subscription Original Research
Volume 01
Issue 01
Received May 30, 2023
Accepted June 14, 2023
Published January 19, 2023
Views: 1,287