String matching and sequence alignment problems are classical problems in Computer Science with extensive applications in di erent branches of science and engineering. These problems are interesting as fundamental computer ...