# Matthew van Eerde's web log

• #### Finding the longest substring which occurs twice in a given string

• 2 Comments

I'm reading Jon Bentley's Programming Pearls and one of the interesting exercises was to find the longest substring which occurs twice in a given string of length n.

There's a naïve solution where you look at every pair of (distinct) indexes (i, j), and calculate the length of the common prefix of the substrings starting at those locations; this is O(n2) assuming that the length of the eventual maximum substring is O(1) (that is, << n.)

Jon shows that there is an O(n log n) algorithm, which is a significant savings if n is large (e.g., War and Peace.)  This involves building an array of all substrings, then sorting them lexically, then walking the sorted array; the trick is that now we only need to check pairs of indexes that correspond to adjacent entries in the array.  That step can be done in O(n) time; the O(n log n) comes from the sorting step.

I wrote up a quick app that implements his suggested algorithm.  Source follows.

// main.cpp

#include <windows.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <search.h>

#define LOG(format, ...) wprintf(format L"\n", __VA_ARGS__)

template<typename T>
class DeleteArrayOnExit {
public:
DeleteArrayOnExit(T *p) : m_p(p), m_canceled(false) {}
~DeleteArrayOnExit() { if (!m_canceled) { delete [] m_p; } }
void Cancel() { m_canceled = true; }
void Swap(T *p) { m_p = p; }
private:
T *m_p;
bool m_canceled;
};

// caller must delete [] the buffer when done with it
LPWSTR ReadFromStdIn();
int __cdecl pwcscmp(const void *pstra, const void *pstrb) {
return wcscmp(*(LPWSTR*)pstra, *(LPWSTR*)pstrb);
}

// returns length of longest common substring
// don't include the null terminator if both strings are identical
// e.g., comlen(banana, bananas) == comlen(banana, banana) == 6
int comlen(LPCWSTR a, LPCWSTR b) {
int i = 0;

// keep going while the strings are the same and not ended
while (a[i] && (a[i] == b[i])) { i++; }

return i;
}

int _cdecl wmain() {
LPWSTR text = ReadFromStdIn();
if (nullptr == text) {
return -__LINE__;
}
DeleteArrayOnExit<WCHAR> deleteText(text);

size_t size = wcslen(text) + 1;
LPWSTR *suffixes = new LPWSTR[size];
if (nullptr == suffixes) {
LOG(L"Could not allocate memory for suffixes");
return -__LINE__;
}
DeleteArrayOnExit<LPWSTR> deleteSuffixes(suffixes);

for (size_t i = 0; i < size; i++) {
suffixes[i] = &text[i];
}

qsort(suffixes, size, sizeof(LPWSTR), pwcscmp);

// find the longest common adjacent pair
LPWSTR szMax = suffixes[0];
size_t lenMax = 0;
for (size_t i = 0; i < size - 1; i++) {
size_t len = comlen(suffixes[i], suffixes[i + 1]);
if (len > lenMax) {
lenMax = len;
szMax = suffixes[i];
}
}

WCHAR *substring = new WCHAR[lenMax + 1];
if (nullptr == substring) {
LOG(L"Could not allocate memory for substring");
return -__LINE__;
}
DeleteArrayOnExit<WCHAR> deleteSubstring(substring);
if (0 != wcsncpy_s(substring, lenMax + 1, szMax, lenMax)) {
LOG(L"wcsncpy_s failed");
return -__LINE__;
}
substring[lenMax] = L'\0';

// intentionally not using LOG to avoid trailing newline
wprintf(L"%s", substring);

return 0;
}

LPWSTR ReadFromStdIn() {
WCHAR *text = new WCHAR[1];
if (nullptr == text) {
LOG(L"Could not allocate memory for text");
return nullptr;
}
DeleteArrayOnExit<WCHAR> deleteText(text);
text[0] = L'\0';

// read a 2 KB chunk
const size_t buffer_size = 1024;
WCHAR *buffer = new WCHAR[buffer_size];
if (nullptr == buffer) {
LOG(L"Could not allocate memory for buffer");
return nullptr;
}
DeleteArrayOnExit<WCHAR> deleteBuffer(buffer);

bool done = false;
do {
if (fgetws(buffer, buffer_size, stdin)) {
size_t size = wcslen(text) + wcslen(buffer) + 1;
WCHAR *new_text = new WCHAR[size];
if (nullptr == new_text) {
LOG(L"Could not allocate memory for new text");
return nullptr;
}
DeleteArrayOnExit<WCHAR> deleteNewText(new_text);

WCHAR *dest = new_text;

if (0 != wcscpy_s(dest, size, text)) {
LOG(L"wcscpy_s failed");
return nullptr;
}
dest += wcslen(text);
size -= wcslen(text);

if (0 != wcscpy_s(dest, size, buffer)) {
LOG(L"wcscpy_s failed");
return nullptr;
}

// that should do it for copying
// now swap new_text => text

delete [] text;
text = new_text;

deleteText.Swap(new_text);
deleteNewText.Cancel();

} else if (feof(stdin)) {
done = true;
} else {
LOG(L"Error reading from STDIN");
return nullptr;
}
} while (!done);

deleteText.Cancel();
return text;
}

• #### Enumerating mixer devices, mixer lines, and mixer controls

• 0 Comments

The WinMM multimedia APIs include an API for enumerating and controlling all the paths through the audio device; things like bass boost, treble control, pass-through audio from your CD player to your headphones, etc.  This is called the "mixer" API and is the forerunner of the IDeviceTopology API.

I wrote a quick app to enumerate all the mixer devices on the system; for each mixer device, enumerate each mixer line (that is, each source and destination); for each mixer line, enumerate all the controls (volume, mute, equalization, etc.); and for each control, query the associated text (if any) and the current value.

Source and binaries attached.

Pseudocode:

mixerGetNumDevs()
for each mixer device
mixerGetDevCaps(dev)
for each destination (line) on the device
mixerGetLineInfo(dest)
mixerGetLineControls(dest)
for each control on the line
if the control supports per-item description
mixerGetControlDetails(control, MIXER_GETCONTROLDETAILSF_LISTTEXT)
log the per-item description
mixerGetControlDetails(control, MIXER_GETCONTROLDETAILSF_VALUE)
log the value(s)

Usage:

>mixerenum.exe
Mixer devices: 5
-- 0: Contoso headset --
Device ID: 0
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Product name: Contoso headset
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_HEADPHONES (5)
Channels: 1
Connections: 2
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target:  --
Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
Device ID: 0
Manufacturer identifier: 65535
Product identifier: 65535
Driver version: 0.0
Product name:
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xffff on a scale of 0x0 to 0xffff
-- 1: HDMI Audio (Contoso --
Device ID: 1
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Product name: HDMI Audio (Contoso
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_DIGITAL (1)
Channels: 1
Connections: 2
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target:  --
Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
Device ID: 0
Manufacturer identifier: 65535
Product identifier: 65535
Driver version: 0.0
Product name:
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xffff on a scale of 0x0 to 0xffff
-- 2: Speakers (Contoso --
Device ID: 2
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Product name: Speakers (Contoso
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_SPEAKERS (4)
Channels: 1
Connections: 2
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target:  --
Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
Device ID: 0
Manufacturer identifier: 65535
Product identifier: 65535
Driver version: 0.0
Product name:
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xffff on a scale of 0x0 to 0xffff
-- 3: Contoso headset --
Device ID: 3
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Product name: Contoso headset
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_WAVEIN (7)
Channels: 1
Connections: 1
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target: Contoso headset --
Type: MIXERLINE_TARGETTYPE_WAVEIN (2)
Device ID: 0
Manufacturer identifier: 1
Product identifier: 101
Driver version: 6.2
Product name: Contoso headset
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xf332 on a scale of 0x0 to 0xffff
-- 4: Microphone (Contoso --
Device ID: 4
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Product name: Microphone (Contoso
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_WAVEIN (7)
Channels: 1
Connections: 1
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target: Microphone (Contoso --
Type: MIXERLINE_TARGETTYPE_WAVEIN (2)
Device ID: 1
Manufacturer identifier: 1
Product identifier: 101
Driver version: 6.2
Product name: Microphone (Contoso
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xf332 on a scale of 0x0 to 0xffff

EDIT September 22 2015: moved source to github https://github.com/mvaneerde/blog/tree/master/mixerenum

• #### Enumerating MIDI devices

• 0 Comments

In addition to audio playback and recording, Windows Multimedia (WinMM) provides a Musical Instrument Digital Interface (MIDI) API.

Here's how to make a list of all the MIDI devices on the system, their capabilities, and the hardware device interface associated with each of them.

Source and binaries attached.

Pseudocode:

midiInGetNumDevs or midiOutGetNumDevs
for each device
midiInGetDevCaps or midiOutGetDevCaps
log device capabilities
midiInMessage or midiOutMessage
with DRV_QUERYDEVICEINTERFACESIZE
and DRV_QUERYDEVICEINTERFACE
log the device interface

Output:

>midienum.exe
midiIn devices: 1
-- 0: USB2.0 MIDI Device --
Device ID: 0
Manufacturer identifier: 65535
Product identifier: 65535
Driver version: 1.6
Product name: USB2.0 MIDI Device
Support: 0x0
Device interface: "\\?\usb#vid_xxxx&pid_yyyy&..."
midiOut devices: 2
-- 0: Microsoft GS Wavetable Synth --
Device ID: 0
Manufacturer identifier: 1
Product identifier: 27
Driver version: 1.0
Product name: Microsoft GS Wavetable Synth
Technology: 7 (MOD_SWSYNTH)
Voices: 32
Notes: 32
Channel mask: 0xffff
Support: 0x1
MIDICAPS_VOLUME
Device interface: ""
-- 1: USB2.0 MIDI Device --
Device ID: 1
Manufacturer identifier: 65535
Product identifier: 65535
Driver version: 1.6
Product name: USB2.0 MIDI Device
Technology: 1 (MOD_MIDIPORT)
Voices: 0
Notes: 0
Channel mask: 0xffff
Support: 0x0
Device interface: "\\?\usb#vid_xxxx&pid_yyyy&..."

(Actual device interface string suppressed.)

Note the Microsoft GS Wavetable Synth device, which is always present.

Why would you want to know the device interface? In our case, because we want to test all the audio-related interfaces of a particular device on the system.

EDIT September 22 2015: moved source to github https://github.com/mvaneerde/blog/tree/master/midienum

• #### Implementing a "listen" command using ISpRecoContext from the Microsoft Speech API

• 2 Comments

Earlier today I posted a quick "say.exe" sample app which you give text and it speaks the text aloud using the text-to-speech part of the Windows Speech API.  It was very straightforward - only 67 lines of C++ code.

It took me a little longer to figure out how to do this "listen.exe" sample app; you run it, speak into the microphone, and it uses the speech-to-text part of the Windows Speech API to print what you're saying to the console.  This is a little more involved: 202 lines of C++ code.

Pseudocode:

CoInitialize()
CoCreateInstance(ISpRecoContext)
pSpRecoContext->SetInterest(recognition events only, thanks)
pSpRecoContext->CreateGrammar()
pSpRecoGrammar->LoadDictation()
pSpRecoGrammar->SetDictationState(active)
while(...) {
wait for a speech event (or the user to press Enter)
pSpRecoContext->GetEvents()
for each speech event {
make sure SPEVENT.eEventId is SPEI_RECOGNITION
event.lParam is an ISpRecoResult
pSpRecoResult->GetText()
print the text
}
}

Usage:

>listen.exe
Speak into the microphone naturally; I will print what I understand.
Press ENTER to quit.
(At this point you start talking into the microphone. Text shows up here shortly after you say it.)

Source and binaries attached.

EDIT September 22 2015: removed source and binaries as this is obsoleted by http://blogs.msdn.com/b/matthew_van_eerde/archive/2014/07/11/using-the-speech-api-to-convert-speech-to-text.aspx

• #### Implementing a "say" command using ISpVoice from the Microsoft Speech API

• 0 Comments

I've known for a while that Microsoft Windows comes with text-to-speech and speech-to-text APIs, which power the Narrator and Speech Recognition features respectively.

This forum post prompted me to mess around with them a little.

I came up with this implementation of a say.exe command which takes a single argument as text, and then uses the ISpVoice text-to-speech API to have the computer speak it aloud.

Source and binaries attached.

Pseudocode:

CoInitialize(nullptr);
CoCreateInstance(ISpVoice)
pSpVoice->Speak(text);

Usage:

>say.exe "Daisy, Daisy; give me your answer, do."

More information on the Speech APIs available here: http://msdn.microsoft.com/en-us/library/ms723627(v=vs.85).aspx

EDIT September 22 2015: removed source and binaries as this is obsoleted by http://blogs.msdn.com/b/matthew_van_eerde/archive/2013/03/13/grabbing-the-output-of-the-microsoft-speech-api-text-to-speech-engine-as-audio-data.aspx

Page 1 of 1 (5 items)