Parsing the longest match substring Post: 302992875

Sponsored Content

Top Forums Shell Programming and Scripting Parsing the longest match substring Post 302992875 by Don Cragun on Thursday 2nd of March 2017 09:42:42 PM

03-02-2017

Registered User

With your sample data, the following seems to do what you want fairly efficiently:

Code:

awk -F// -v OFS="\t\t" '
BEGIN {	M = 0
	m = 32000
}
FNR == NR {
	if((l = length($0)) in pat) {
		pat[l] = pat[l] "|" $0
		#printf("appending pattern: pat[%d]=\"%s\"\n", l, pat[l])
	} else {pat[l] = $0
		#printf("adding pattern: pat[%d]=\"%s\"\n", l, pat[l])
		if(l > M)
			M = l
		if(l < m)
			m = l
	}
	next
}
#FNR == 1 {
#	for(i = M; i >= m; i--)
#		if(i in pat)
#			printf("pat[%d]=\"%s\"\n", i, pat[i])
#}
{	short = length($1) < length($2) ? 1 : 2
	for(i = M; i >= m; i--)
		if(i in pat && match($short, pat[i])) {
			print $0, substr($short, RSTART, RLENGTH)
			next
		}
	print $0, "No match"
}' primary scrambled

but I don't have any good way to test how this might work if you have EREs with thousands of patterns to be matched as alternatives in a single ERE. With your sample inputs, it produces:

Code:

())[pt22dx]dfdfs//(dsgfspp22dx/pg22dx)-signal		pt22dx
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@--		pp22dx
signal-ef##$@pp22//[[((dsgfspp22dx/pg22dx)-signal[(\pp22dx)-@@----B-@--		pp22

as its output (which I think meets your requirements).

PS: Depending on the distribution of the lengths of your patterns, you might want to try the code I used in post #2 in this thread to sort the lengths and avoid processing lengths that don't exist in your data. I assume you won't have any problem merging the code from these two suggestions to get what you need.

Last edited by Don Cragun; 03-02-2017 at 11:09 PM.. Reason: Add PS.

This User Gave Thanks to Don Cragun For This Post:

Don Cragun

View Public Profile for Don Cragun

Find all posts by Don Cragun

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Finding longest common substring among filenames

I will be performing a task on several directories, each containing a large number of files (2500+) that follow a regular naming convention: YYYY_MM_DD_XX.foo_bar.A.B.some_different_stuff.EXT What I would like to do is automatically discover the part of the filenames that are common to all...

2. Shell Programming and Scripting

Parsing file to match strings

I have a file with the following format 12g data/datasets/cct 8g data/dataset/cct 10 g data/two 5g data/something_different 10g something_different 5g data/two is there a way to loop through this...

3. Shell Programming and Scripting

Awk Array doesnt match for substring

Awk Array doesnt match for substring nawk -F"," 'FNR==NR{a=$2 OFS $3;next} a{print $1,$2,a}' OFS="," file1 file2 I want cluster3 in file1 to match with cluster3int in file2 output getting: Output required: Help is appreciated

4. Shell Programming and Scripting

shell script: longest match from right?

Return the position of matched string from right, awk match can do from left only. e.g return pos 7 for search string "service" from "AA-service" or return the matched string "service", then caculate the string length. Thanks!.

5. Shell Programming and Scripting

Substring match

Hi, I want to find a file / directory with the name xxxxCELLxxx in the given path. The CELL is can be either in a UPPER or lower case. Thanks

6. Shell Programming and Scripting

Longest word in a file

I am trying to write a command on just one line, i.e seperated by ';' and '|' etc, that finds the number of characters in the longest word of a file, preferably using the 'tr' and 'wc' commands. i no that wc shows the number of lines words and characters in a file but im not sure how to use it...

7. UNIX for Dummies Questions & Answers

Deleting files based on Substring match

In folder there are files (eg ABS_18APR2012_XYZ.csv DSE_17APR2012_ABE.csv) . My requirement is to delete all the files except today's timestamp I tried doing this to list all the files not having today's date timestamp #!/bin/ksh DATE=`date +"%d%h%Y"` DIR=/data/rfs/...

8. Shell Programming and Scripting

Match substring from a column of the second file

I want to merge the lines by matching substring of the first file with first column of the second file. file1: S00739A_ACAGTG_L001_R1.fq.gz S00739A_ACAGTG_L001_R2.fq.gz S00739B_GCCAAT_L001_R1.fq.gz S00739B_GCCAAT_L001_R2.fq.gz S00739D_GTGAAA_L001_R1.fq.gz S00739D_GTGAAA_L001_R2.fq.gz...

9. Shell Programming and Scripting

Match text to lines in a file, iterate backwards until text or text substring matches, print to file

hi all, trying this using shell/bash with sed/awk/grep I have two files, one containing one column, the other containing multiple columns (comma delimited). file1.txt abc12345 def12345 ghi54321 ... file2.txt abc1,text1,texta abc,text2,textb def123,text3,textc gh,text4,textd...

10. UNIX for Beginners Questions & Answers

Replace substring by longest string in common field (awk)

Hi, Let's say I have a pipe-separated input like so: name_10|A|BCCC|cat_1 name_11|B|DE|cat_2 name_10|A|BC|cat_3 name_11|B|DEEEEEE|cat_4 Using awk, for records with common field 2, I am trying to replace all the shortest substrings by the longest string in field 3. In order to get the...

LEARN ABOUT NETBSD

memmem

MEMMEM(3)						   BSD Library Functions Manual 						 MEMMEM(3)

NAME

     memmem -- locate substring in byte string

LIBRARY

     Standard C Library (libc, -lc)

SYNOPSIS

     #include <string.h>

     void *
     memmem(const void *block, size_t blen, const void *pat, size_t plen);

DESCRIPTION

     The memmem() function locates the first occurrence of the binary string pat of size plen bytes in the byte string block of size blen bytes.

RETURN VALUES

     The memmem() function returns a pointer to the substring located, or NULL if no such substring exists within block.

     If plen is zero, block is returned, i.e. a zero length pat is deemed to match the start of the string, as with strstr(3).

SEE ALSO

     bm(3), memchr(3), strchr(3), strstr(3)

STANDARDS

     The memmem() function is not currently standardized.  However, it is meant to be API compatible with functions in FreeBSD and Linux.

HISTORY

     memmem() first appeared in the Free Software Foundation's glibc library.

BSD
								  March 12, 2005							       BSD

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Finding longest common substring among filenames

Discussion started by: cmcnorgan

2. Shell Programming and Scripting

Parsing file to match strings

Discussion started by: yawalias

3. Shell Programming and Scripting

Awk Array doesnt match for substring

Discussion started by: pinnacle

4. Shell Programming and Scripting

shell script: longest match from right?

Discussion started by: honglus