50145. Sub Linked List

I'm a slow walker, but I never walk backwards.

Task Description

You are given two strings $text$ and $pattern$, which are implemented as linked lists. The length of text is always larger than the length of pattern. Now you need to determine if the pattern is a substring/subsequence of the text.

The first function is to determine if the pattern is a substring of the text. A pattern is a substring of the text if it appears in the text as $consecutive$ letters. So you need to find out the location of the pattern in the text and compute the sum of the index of all the characters. If the pattern appears more than once in the text, report the one with the $smallest$ sum of indices. Please refer to the following figure for an illustration. Note that index starts from 0.

samplesample

The second function determine if the pattern is a subsequence of the text. This is similar to substring but the characters of the pattern do $not$ need to be consecutive. Again there could be more than subsequences, and you need to output the one with the smallest sum of indices. Please refer to the following figure. Note that index starts from 0.

samplesample

The linked list node and the functions you need to implement are defined in sub.h.

typedef struct Node
{
    char c;
    struct Node *next;
}Node;
void substring(Node* text, Node* pattern);
void subsequence(Node* text, Node* pattern);

You may use the following main function to test your functions.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "sub.h"
 
Node* insert(Node* root, char c)
{
    if(root == NULL){
        root = (Node*)malloc(sizeof(Node));
        root->c = c;
        root->next = NULL;
        return root;
    }
    root->next = insert(root->next, c);
    return root;
}
int main(int argc, char const *argv[])
{
    char tmp = '\n';
    int N, M, i, act;
    Node *text = NULL, *pattern = NULL, *cur = NULL;
 
    scanf("%d%d", &act, &N);
    while(isspace(tmp)) scanf("%c", &tmp);
    text = insert(text, tmp);
    cur = text;
    for(i = 0; i < N-1; i++){
        scanf("%c", &tmp);
        cur->next = insert(cur->next, tmp);
        cur = cur->next;
    }
 
    scanf("%d", &M);
    tmp = '\n';
    while(isspace(tmp)) scanf("%c", &tmp);
    pattern = insert(pattern, tmp);
    cur = pattern;
    for(i = 0; i < M-1; i++){
        scanf("%c", &tmp);
        cur->next = insert(cur->next, tmp);
        cur = cur->next;
    }
    if (!act)
        substring(text, pattern);
    else
        subsequence(text, pattern);
    return 0;
}

Input Format

The first line has one integer, and it is 0 for substring computation and 1 for subsequence computation. The second line has the length of text. The third line has the text. The fourth line has the length of the pattern. The fifth line has the the pattern.

Output Format

Output the smallest sum of indices of the characters as substring/subsequence.

Subtasks

  • 10 points: The length of the pattern is exactly two, and the task is substring.
  • 40 points: The length of the pattern is more than two, and the task is substring.
  • 10 points: The length of the pattern is exactly two, and the task is subsequence.
  • 40 points: The length of the pattern is more than two, and the task is subsequence.

Sample Input 1

0
23
sixcnxepfwpiaqjmqzwwxom
2
pi

Sample output 1

21

Sample Input 2

0
24
levqbmnjolvbgpwnjlfufibf
5
njlfu

Sample output 2

85

Sample Input 3

1
23
ezfrocfuzvxeklclfgzjpza
2
fz

Sample output 3

10

Sample Input 4

1
24
czacffcfpgvhsxnsnrwfjgsr
5
zanjg

Sample output 4

58

Discussion