source: CIVL/examples/verifyThisProblems/quantifiedComp.cvl@ 0e12c94

/*
author: Yihao

Link(LCP.zip): http://fm2012.verifythis.org/challenges

This is a verifyThis problem in 2012.
This task asks you to get the longest common prefix of
two subStrings.

Input: an integer array arr, the length of the array, and two indices x and y.

command: civl verify quantifiedComp.cvl

result: the problem is solved
*/

#include <civlc.cvh>
#include <assert.h>

$input int n=3;
$input int x;
$input int y;
$input int X1[n];

$assume (x < n && y < n && x >=0 && y>=0);

int lcp (int *arr, int n, int x, int y) {
  int l=0;

  while (x+l<n && y+l<n && arr[x+l]==arr[y+l]) {
      l++;
  }
  return l;
}

void main() {
  int result = lcp(X1, n, x, y);
  
  assert($forall {int i | i>=0 && i<result} X1[x+i] == X1[y+i]);
}