How do we achieve "substring-match" under O(n) time?

Posted by Pacerier on Stack Overflow See other posts from Stack Overflow or by Pacerier
Published on 2011-11-17T09:06:44Z Indexed on 2012/09/16 15:38 UTC
Read the original article Hit count: 255

Filed under:

java

|

string

|

algorithm

|

language-agnostic

I have an assignment that requires reading a huge file of random inputs, for example:

Adana 
Izmir Adnan Menderes Apt
Addis Ababa
Aden
ADIYAMAN
ALDAN
Amman Marka Intl Airport
Adak Island
Adelaide Airport
ANURADHAPURA
Kodiak Apt
DALLAS/ADDISON
Ardabil 
ANDREWS AFB
etc..

If I specify a search term, the program is supposed to find the lines whereby a substring occurs. For example, if the search term is "uradha", the program is supposed to show ANURADHAPURA. If the search term is "airport", the program is supposed to show Amman Marka Intl Airport, Adelaide Airport

A quote from the assignment specs: "You are to program this application taking efficiency into account as though large amounts of data and processing is involved.."

I could easily achieve this functionality using a loop but the performance would be O(n). I was thinking of using a trie but it seems to only work if the substring starts from index 0.

I was wondering what solutions are there which gives a performance better than O(n)?

© Stack Overflow or respective owner

Related posts about java

Tomcat 6: Access Control Exception?

as seen on Server Fault - Search for 'Server Fault'
I'm trying to setup a tomcat6 server, and I'm trying to match another setup someone else established. However, my deployment (default Ubuntu install) uses a policy.d/ directory structure, and the established server just uses a catalina.policy file. I've tried setting every entry in policy.d to match… >>> More
Problem in creation MDB Queue connection at Jboss StartUp

as seen on Stack Overflow - Search for 'Stack Overflow'
I am not able to create a Queue connection in JBOSS4.2.3GA Version & Java1.5, as I am using MDB as per the below details. I am putting this MDB in a jar file(named utsJar.jar) and copied it in deploy folder of JBOSS, In the test env. this MDB works well but in another env. [ env settings and… >>> More
failing to establish connection between Postgres db and gwt

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am using Postgres and gwt 2.0 for one of my applications. I am facing problem connecting to the database. When I try to connect it gives "ClassNotFoundException". Here is what I get when I try to connect to database: java.lang.ClassNotFoundException: org.postgresql.Driver at java.net… >>> More
failing to establish connection between postgre db and gwt

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, For i am using postgre and gwt 2.0 for one of my applications. I am facing problem connecting to the database. When i try to connect it gives "ClassNotFoundException". Here is what i get when i try to connect to database: java.lang.ClassNotFoundException: org.postgresql.Driver at java.net… >>> More
Migration and deployement problems JBoss 4.2.2.GA to JBoss 6.0.0.M2

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I'm trying to migrate an application running on JBoss 4.2.2.GA to JBoss 6.0.0.M2 I give you some log to explain my problem : boot.log : 2010-03-16 09:59:29,406 ERROR [org.jboss.system.server.profileservice.ProfileServiceBootstrap] (Thread-2) Failed to load profile: Summary of incomplete deployments… >>> More

Related posts about string

Read array dump output and generates the correspondent XML file

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, The text below is the dump of a multidimensional array, dumped by the var_dump() PHP function. I need a Java function that reads a file with a content like this (attached) and returns it in XML. For a reference, in site http://pear.php.net/package/Var_Dump/ you can find the code (in PHP) that… >>> More
Formatting a date string when the string sits inside another string

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I'm trying to figure out a way to format a date string that sits inside string using javascript. The string can be: "hello there From 2010-03-04 00:00:00.0 to 2010-03-31 00:00:00.0" or "stuff like 2010-03-04 20:00:00.0 and 2010-03-31 00:00:02.0 blah blah" I'd like it to end up like: "stuff… >>> More
Using String+string+string vs using string.replace

as seen on Stack Overflow - Search for 'Stack Overflow'
A colleague told me that using the following method: string url = "SomeURL"; string ext = "SomeExt"; string sub = "SomeSub"; string subSub = "moreSub"; string Url = @"http://www." + Url +@"/"+ ext +@"/"+ sub + subSub; is not efficenet (takes more resources) and it is preferred to use the… >>> More
vb.net string concatenation string + function output + string = string + function output and no more

as seen on Stack Overflow - Search for 'Stack Overflow'
The following output produces a string with no closing xml tag. m_rFlight.Layout = m_rFlight.Layout + "<G3Grid:Spots>" + Me.gvwSpots.LayoutToString() + "</G3Grid:Spots>" This following code works correctly m_rFlight.Layout = m_rFlight.Layout + "<G3Grid:Spots>" + Me.gvwSpots.LayoutToString() m_rFlight… >>> More
Trying to convert simple midlet application to Android application but running into problems.

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi I am trying to do some threading in Android so I took an old threading assignment I had done fora midlet and took out the midlet code and replaced it with android code(such as textview). package com.assignment1; import android.app.Activity; import android.os.Bundle; import android.widget.TextView; public… >>> More