Skip to content

Instantly share code, notes, and snippets.

@saleemkce
Last active January 2, 2016 09:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save saleemkce/8283631 to your computer and use it in GitHub Desktop.
Save saleemkce/8283631 to your computer and use it in GitHub Desktop.
Given a paragraph of text, write a program to find the first shortest sub-segment that contains each of the given k words at least once. A segment is said to be shorter than other if it contains less number of words.
<?php
/*
Given a paragraph of text, write a program to find the first shortest sub-segment that contains each of the given k words at least once. A segment is said to be shorter than other if it contains less number of words.
Ignore characters other than [a-z][A-Z] in the text. Comparison between the strings should be case-insensitive.
If no sub-segment is found then the program should output “NO SUBSEGMENT FOUND”.
Input format :
First line of the input contains the text.
Next line contains k , the number of words given to be searched.
Each of the next k lines contains a word.
Output format :
Print first shortest sub-segment that contains given k words , ignore special characters, numbers.If no sub-segment is found it should return “NO SUBSEGMENT FOUND”
Sample Input :
This is a test. This is a programming test. This is a programming test in any language.
4
this
a
test
programming
Sample Output :
a programming test This
Explanation :
In this test case segment "a programming test. This" contains given four words. You have to print without special characters, numbers so output is "a programming test This". Another segment "This is a programming test." also contains given four words but have more number of words.
Constraint :
Total number of character in a paragraph will not be more than 200,000.
0 < k <= no. of words in paragraph.
0 < Each word length < 15
*/
$stdin = fopen('php://stdin', 'r');
$line = trim(fgets(STDIN));
if(strlen($line)>200000)
{
die("Please enter your input below 200000 characters!");
}
$checkWords = explode(" ", $line);
foreach($checkWords as $wordConstraint)
{
if(strlen($wordConstraint) > 14 || strlen($wordConstraint) < 1){
die("Word length cannot be more than 14 characters!");
}
}
$arr1 = array();
fscanf(STDIN, "%d\n", $numbb);
if(!preg_match("/^[0-9]+$/", $numbb))
{
die("Enter the count in digits(number)!");
}
if(preg_match("/^[0-9]+$/", $numbb))
{
if(($numbb == 0) || ($numbb > str_word_count($line)))
{
die("Number cannot be 0 or greater than ".str_word_count($line)."!");
}
}
$orgArray = array();
$orgArray = str_split($line);
for($op = 0; $op < $numbb; $op++)
{
$uInput = trim(fgets(STDIN)); /* processing here input */
if(strlen($uInput) < 1 || strlen($uInput) >14)
{
die("Word length cannot be more than 14 characters! Loop inside");
}
else if(preg_match('/\s/',$uInput))
{
die("only one word allowed per line!");
}
else if (strpos($line, $uInput) == false)
{
$avails = 0;
}
$dimTempArray = array();
$dimTempArray = str_split($uInput);
$a = 0; $newGotAs = ""; $lastNew = "";
$tempLen = strlen($uInput);
$tempLen = strlen($uInput);
for($oo = 0; $oo < strlen($line); $oo++)
{
if( (strcasecmp($dimTempArray[$a], $orgArray[$oo]) == 0) )
{
$lastNew .= $orgArray[$oo];
++$a;
--$tempLen;
if($tempLen == 0)
{
$newGotAs = $lastNew; break;
}
}
else if(!ctype_alpha( $orgArray[$oo] ))
{
continue;
}
else
{
$tempLen = strlen($uInput); $lastNew = ""; $a = 0;
}
}/* processing here input */
$uInput = trim($newGotAs);
array_push($arr1, $uInput);
}
$text = array();
$count_line = strlen($line);
for($i = 0; $i < $count_line; $i++)
{
$text[$i] = $line[$i];
}
$result1 = array_dim2_perm($arr1, array(), true);
$bbb = count($arr1); $aaa = factorial($bbb);
$successWord = array(); $successWordLen = array();
for($a = 0; $a < $aaa; $a++)
{
$tempInner = "";
for($c = 0; $c < $bbb; $c++)
{
$tempInner .= $result1[$a][$c]." ";
if($c == ($bbb-1))
{
$tempInner = substr($tempInner, 0, -1);
$successWord[$a] = $tempInner;
$successWordLen[$a] = strlen($tempInner);
}
}
}
$successWordArray = array();
for($as = 0; $as < $aaa; $as++)
{
$successWordArray[$as] = str_split($successWord[$as]);
}
$a = 0;$receivedOutput = "";$gotAs = "";$avails = 0; $tempFinal = "";
for($end = 0; $end < $aaa; $end++)
{
$tempLen = $successWordLen[$end];
for($ze = 0; $ze < $count_line; ++$ze)
{
if( (strcasecmp($successWordArray[$end][$a], $text[$ze]) == 0) )
{
$receivedOutput .= $successWordArray[$end][$a];
++$a;
--$tempLen;
if($tempLen == 0)
{
$gotAs = $receivedOutput;
if($gotAs == $successWord[$end])
{
fwrite(STDOUT, $gotAs); $avails = 1; break;
}
else
{
fwrite(STDOUT, "NO SUBSEGMENT FOUND");
}
break;
}
}
else if(!ctype_alpha( $text[$ze] ))
{
continue;
}
else
{
$tempLen = $successWordLen[$end]; $receivedOutput = ""; $a = 0;
}
}
/*if($gotAs == $successWord[$end])
{
fwrite(STDOUT, $gotAs); $avails = 1; break;
}
else
{
$avails = 0;
}*/
$a = 0; $receivedOutput = ""; $gotAs = "";
}
/*if($avails == 0)
{
fwrite(STDOUT, "NO SUBSEGMENT FOUND");
}*/
function factorial ($n)
{
if($n <= 1)
{
return 1;
}
else
{
return $n * factorial($n - 1);
}
}
function array_dim2_perm($dataPos, $possiblle = array(), $New = false) {
static $possibleArray = array();
if($New)
$possibleArray = array();
if (empty($dataPos)) {
$possibleArray[]=$possiblle;
} else {
for ($i = count($dataPos) - 1; $i >= 0; --$i) {
$newitems = $dataPos;
$newperms = $possiblle;
list($foo) = array_splice($newitems, $i, 1);
array_unshift($newperms, $foo);
array_dim2_perm($newitems, $newperms);
}
return $possibleArray;
}
}?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment