Pattern Matching

파일 in.txt 에 다음과 같이 r (row 의 개수), c(column 개수), 그리고 r x c 개의 정수가 저장되어 있다.
r c
a0,0 a0,1 a0,2 … a0,c-1
a1,0 a1,1 a1,2 … a1,c-1
a2,0 a2,1 a2,2 … a2,c-1
…
ar-1,0 a r-1,1 a r-1,2 … a r-1,c-1
파일 key.txt 는 다음과 같이 구성된다.
n x0 x1 x2 … xn-1
여기에서 xi는 정수이고, 1 ≤ n ≤ c 이다.

• 단계 1. in.txt 에 저장된 정수들을 dynamic memory allocation 을 이용하여 r x c 크기의 2 차원 정수
  array 인 M 에 저장한다. (row-major order 로 가정)
• 단계 2. key.txt 에 저장된 n 개의 정수를 1 차원 array S 에 저장한다.
• 단계 3. S 가 M 에 속한 한 개의 행(row) 내에 포함되었는지 판단하는 pattern match 프로그램을 작성하라.
  S 가 M 에 포함되었으면 S 가 시작되는 array M 의 (행의 index, 열의 index) 를 화면에 출력한다.
  포함되지 않았으면 (-1, -1)을 출력한다.

  가정: S 가 M 에 포함된 경우에는, 한 번만 포함된다. 즉, S 의 정수열이 M 내에 여러 번 존재하지 않는다.

#include <iostream>
#include <fstream>

using namespace std;

int pattern(int** s, int* keyArr, int rows, int cols, int keys) {
	int zero = 0, a, b;
	for(int i = 0; i < rows; i++){
		//10x10 2차원 배열에 키의 개수가 3개면 cols[7] 까지만 읽기
		for (int j = 0; j <= cols - keys; j++) {
			for (int k = j; k < j + keys; k++) {
				//m 배열에 저장된 키와 cols의 요소를 비교
				if (s[i][k] == keyArr[zero]) {
					zero++; // 값이 같다면 계속 비교
					}
				if (zero == keys) { //키를 다 찾으면
					printf("(%d, %d)", i, j); //키가 시작하는 인덱스 출력
					return 0;
				}
			}
			zero = 0; //값이 다른경우 zero 초기화
		}
	}
	if (zero < keys) {
		printf("(-1, -1)");
	}//키가 발견되지 않으면 (-1, -1) 출력
}
int main() {
	fstream in("in.txt"); fstream key("key.txt");

	int rows = 0, cols = 0; int keys = 0; int* keyArr;
	in >> rows; in >> cols;

	int** s; //2차원 배열 포인터

	s = (int**)malloc(sizeof(int*) * rows);

	for (int i = 0; i < rows; i++) {
		s[i] = (int*)malloc(sizeof(int) * cols);
	}
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			in >> s[i][j];
		}
	}
	key >> keys;
	keyArr = (int*)malloc(sizeof(int) * keys);
	for (int i = 0; i < keys; i++) {
		key >> keyArr[i];
	}
	pattern(s, keyArr, rows, cols, keys);
}