#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>           /* Definition of AT_* constants */
#include <errno.h>
#include <sys/epoll.h>

int main(void) {
    int fds[2];

    if (mkfifo("./fifo1", 0644) < 0) {
        perror("mkfifo()");
    };

    if (mkfifo("./fifo2", 0644) < 0) {
        perror("mkfifo()");
    };

    if ((fds[0] = open("./fifo1", O_RDONLY|O_NONBLOCK, 0644)) < 0)
        perror("open()");

    if ((fds[1] = open("./fifo2", O_RDONLY|O_NONBLOCK, 0644)) < 0)
        perror("open()");

    int epfd;
    struct epoll_event ev[2] = {0};
    struct epoll_event evlist[2];

    epfd = epoll_create(2);
    if (epfd == -1) {
        perror("epoll_create");
        exit(EXIT_FAILURE);
    }
    ev[0].data.fd = fds[0];
    ev[0].events = EPOLLIN;
    if (epoll_ctl(epfd, EPOLL_CTL_ADD, fds[0], &ev[0]) == -1) {
        perror("epoll_ctl");
        exit(EXIT_FAILURE);
    }

    ev[1].data.fd = fds[1];
    ev[1].events = EPOLLIN;
    if (epoll_ctl(epfd, EPOLL_CTL_ADD, fds[1], &ev[1]) == -1) {
        perror("epoll_ctl");
        exit(EXIT_FAILURE);
    }

    while (1) {
        int ready = epoll_wait(epfd, evlist, 2, -1);
        if (ready == -1) {
            if (errno == EINTR)
                continue;
            else {
                perror("epoll_wait()");
                exit(EXIT_FAILURE);
            }
        }
        printf("ready: %d\n", ready);
    }
    // char buf[4096] = {0};
    // ssize_t n;
    // ssize_t result;
    // size_t remains;
    // for (;;) {
    //     char *p = buf;
    //     n = 0;
    //     remains = 4096;
    //     while (remains > 0) {
    //         if ((result = read(fds[0], p, remains)) == -1) {
    //             if (errno == EAGAIN || errno == ETIMEDOUT) {
    //                 sleep(1);
    //                 continue;
    //             } else {
    //                 perror("read()");
    //                 exit(EXIT_FAILURE);
    //             }
    //         }
    //         n += result;
    //         remains -= result;
    //         printf("%s", p);
    //         p += n;
    //     }
    // }
}

/*
 *   File:   fanotify-example.c
 *   Date:   Fri Nov 15 14:55:49 2013
 *   Author: Aleksander Morgado <aleksander@lanedo.com>
 *
 *   A simple tester of fanotify in the Linux kernel.
 *
 *   This program is released in the Public Domain.
 *
 *   Compile with:
 *     $> gcc -o fanotify-example fanotify-example.c
 *
 *   Run as:
 *     $> ./fanotify-example /path/to/monitor /another/path/to/monitor ...
 */

/* Define _GNU_SOURCE, Otherwise we don't get O_LARGEFILE */
#define _GNU_SOURCE

#include <stdio.h>
#include <signal.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <poll.h>
#include <errno.h>
#include <limits.h>
#include <sys/stat.h>
#include <sys/signalfd.h>
#include <fcntl.h>

#include <linux/fanotify.h>

/* Structure to keep track of monitored directories */
typedef struct {
  /* Path of the directory */
  char *path;
} monitored_t;

/* Size of buffer to use when reading fanotify events */
#define FANOTIFY_BUFFER_SIZE 8192

/* Enumerate list of FDs to poll */
enum {
  FD_POLL_SIGNAL = 0,
  FD_POLL_FANOTIFY,
  FD_POLL_MAX
};

/* Setup fanotify notifications (FAN) mask. All these defined in fanotify.h. */
static uint64_t event_mask =
  (FAN_ACCESS |         /* File accessed */
   FAN_MODIFY |         /* File modified */
   FAN_CLOSE_WRITE |    /* Writtable file closed */
   FAN_CLOSE_NOWRITE |  /* Unwrittable file closed */
   FAN_OPEN |           /* File was opened */
   FAN_ONDIR |          /* We want to be reported of events in the directory */
   FAN_EVENT_ON_CHILD); /* We want to be reported of events in files of the directory */

/* Array of directories being monitored */
static monitored_t *monitors;
static int n_monitors;

static char *
get_program_name_from_pid (int     pid,
			   char   *buffer,
			   size_t  buffer_size)
{
  int fd;
  ssize_t len;
  char *aux;

  /* Try to get program name by PID */
  sprintf (buffer, "/proc/%d/cmdline", pid);
  if ((fd = open (buffer, O_RDONLY)) < 0)
    return NULL;

  /* Read file contents into buffer */
  if ((len = read (fd, buffer, buffer_size - 1)) <= 0)
    {
      close (fd);
      return NULL;
    }
  close (fd);

  buffer[len] = '\0';
  aux = strstr (buffer, "^@");
  if (aux)
    *aux = '\0';

  return buffer;
}

static char *
get_file_path_from_fd (int     fd,
		       char   *buffer,
		       size_t  buffer_size)
{
  ssize_t len;

  if (fd <= 0)
    return NULL;

  sprintf (buffer, "/proc/self/fd/%d", fd);
  if ((len = readlink (buffer, buffer, buffer_size - 1)) < 0)
    return NULL;

  buffer[len] = '\0';
  return buffer;
}

static void
event_process (struct fanotify_event_metadata *event)
{
  char path[PATH_MAX];

  printf ("Received event in path '%s'",
          get_file_path_from_fd (event->fd,
                                   path,
                                   PATH_MAX) ?
          path : "unknown");
  printf (" pid=%d (%s): \n",
          event->pid,
          (get_program_name_from_pid (event->pid,
                                        path,
                                        PATH_MAX) ?
           path : "unknown"));

  if (event->mask & FAN_OPEN)
    printf ("\tFAN_OPEN\n");
  if (event->mask & FAN_ACCESS)
    printf ("\tFAN_ACCESS\n");
  if (event->mask & FAN_MODIFY)
    printf ("\tFAN_MODIFY\n");
  if (event->mask & FAN_CLOSE_WRITE)
    printf ("\tFAN_CLOSE_WRITE\n");
  if (event->mask & FAN_CLOSE_NOWRITE)
    printf ("\tFAN_CLOSE_NOWRITE\n");
  fflush (stdout);

  close (event->fd);
}

static void
shutdown_fanotify (int fanotify_fd)
{
  int i;

  for (i = 0; i < n_monitors; ++i)
    {
      /* Remove the mark, using same event mask as when creating it */
      fanotify_mark (fanotify_fd,
                     FAN_MARK_REMOVE,
                     event_mask,
                     AT_FDCWD,
                     monitors[i].path);
      free (monitors[i].path);
    }
  free (monitors);
  close (fanotify_fd);
}

static int
initialize_fanotify (int          argc,
		     const char **argv)
{
  int i;
  int fanotify_fd;

  /* Create new fanotify device */
  if ((fanotify_fd = fanotify_init (FAN_CLOEXEC,
                                    O_RDONLY | O_CLOEXEC | O_LARGEFILE)) < 0)
    {
      fprintf (stderr,
               "Couldn't setup new fanotify device: %s\n",
               strerror (errno));
      return -1;
    }

  /* Allocate array of monitor setups */
  n_monitors = argc - 1;
  monitors = malloc (n_monitors * sizeof (monitored_t));

  /* Loop all input directories, setting up marks */
  for (i = 0; i < n_monitors; ++i)
    {
      monitors[i].path = strdup (argv[i + 1]);
      /* Add new fanotify mark */
      if (fanotify_mark (fanotify_fd,
                         FAN_MARK_ADD,
                         event_mask,
                         AT_FDCWD,
                         monitors[i].path) < 0)
        {
          fprintf (stderr,
                   "Couldn't add monitor in directory '%s': '%s'\n",
                   monitors[i].path,
                   strerror (errno));
          return -1;
        }

      printf ("Started monitoring directory '%s'...\n",
              monitors[i].path);
    }

  return fanotify_fd;
}

static void
shutdown_signals (int signal_fd)
{
  close (signal_fd);
}

static int
initialize_signals (void)
{
  int signal_fd;
  sigset_t sigmask;

  /* We want to handle SIGINT and SIGTERM in the signal_fd, so we block them. */
  sigemptyset (&sigmask);
  sigaddset (&sigmask, SIGINT);
  sigaddset (&sigmask, SIGTERM);

  if (sigprocmask (SIG_BLOCK, &sigmask, NULL) < 0)
    {
      fprintf (stderr,
               "Couldn't block signals: '%s'\n",
               strerror (errno));
      return -1;
    }

  /* Get new FD to read signals from it */
  if ((signal_fd = signalfd (-1, &sigmask, 0)) < 0)
    {
      fprintf (stderr,
               "Couldn't setup signal FD: '%s'\n",
               strerror (errno));
      return -1;
    }

  return signal_fd;
}

int
main (int          argc,
      const char **argv)
{
  int signal_fd;
  int fanotify_fd;
  struct pollfd fds[FD_POLL_MAX];

  /* Input arguments... */
  if (argc < 2)
    {
      fprintf (stderr, "Usage: %s directory1 [directory2 ...]\n", argv[0]);
      exit (EXIT_FAILURE);
    }

  /* Initialize signals FD */
  if ((signal_fd = initialize_signals ()) < 0)
    {
      fprintf (stderr, "Couldn't initialize signals\n");
      exit (EXIT_FAILURE);
    }

  /* Initialize fanotify FD and the marks */
  if ((fanotify_fd = initialize_fanotify (argc, argv)) < 0)
    {
      fprintf (stderr, "Couldn't initialize fanotify\n");
      exit (EXIT_FAILURE);
    }

  /* Setup polling */
  fds[FD_POLL_SIGNAL].fd = signal_fd;
  fds[FD_POLL_SIGNAL].events = POLLIN;
  fds[FD_POLL_FANOTIFY].fd = fanotify_fd;
  fds[FD_POLL_FANOTIFY].events = POLLIN;

  /* Now loop */
  for (;;)
    {
      /* Block until there is something to be read */
      if (poll (fds, FD_POLL_MAX, -1) < 0)
        {
          fprintf (stderr,
                   "Couldn't poll(): '%s'\n",
                   strerror (errno));
          exit (EXIT_FAILURE);
        }

      /* Signal received? */
      if (fds[FD_POLL_SIGNAL].revents & POLLIN)
        {
          struct signalfd_siginfo fdsi;

          if (read (fds[FD_POLL_SIGNAL].fd,
                    &fdsi,
                    sizeof (fdsi)) != sizeof (fdsi))
            {
              fprintf (stderr,
                       "Couldn't read signal, wrong size read\n");
              exit (EXIT_FAILURE);
            }

          /* Break loop if we got the expected signal */
          if (fdsi.ssi_signo == SIGINT ||
              fdsi.ssi_signo == SIGTERM)
            {
              break;
            }

          fprintf (stderr,
                   "Received unexpected signal\n");
        }

      /* fanotify event received? */
      if (fds[FD_POLL_FANOTIFY].revents & POLLIN)
        {
          char buffer[FANOTIFY_BUFFER_SIZE];
          ssize_t length;

          /* Read from the FD. It will read all events available up to
           * the given buffer size. */
          if ((length = read (fds[FD_POLL_FANOTIFY].fd,
                              buffer,
                              FANOTIFY_BUFFER_SIZE)) > 0)
            {
              struct fanotify_event_metadata *metadata;

              metadata = (struct fanotify_event_metadata *)buffer;
              while (FAN_EVENT_OK (metadata, length))
                {
                  event_process (metadata);
                  if (metadata->fd > 0)
                    close (metadata->fd);
                  metadata = FAN_EVENT_NEXT (metadata, length);
                }
            }
        }
    }

  /* Clean exit */
  shutdown_fanotify (fanotify_fd);
  shutdown_signals (signal_fd);

  printf ("Exiting fanotify example...\n");

  return EXIT_SUCCESS;
}

// デジタル7番ピン
int sensorPin = 7;

void setup() 
{
  Serial.begin(9600);
}

void loop() 
{
  // デフォルト0, 触れていたら1
  int sensorValue = digitalRead(sensorPin);
  Serial.println(sensorValue );
  delay(1000);
}

#include <sys/eventfd.h>
#include <sys/epoll.h>
#include <sys/types.h>
#include <inttypes.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>

typedef struct cgroup_ctrl {
    int efd;    /* event fd */
    int fd;     /* file fd */
} cgroup_ctrl_t;

struct list {
    struct list *next;
    uint8_t blob[1];
};

/*
 * Utity method that allows to write to a specified "cgroup/file"
 * the string ctrl with size ctrl_size.
 */
static int __cgroup_write (const char *cgroup,
                           const char *file,
                           const char *ctrl,
                           size_t ctrl_size)
{
    char path[PATH_MAX];
    ssize_t wr;
    int fd;

    snprintf(path, PATH_MAX, "%s/%s", cgroup, file);
    if ((fd = open(path, O_WRONLY)) < 0) {
        fprintf(stderr, "%s\n", path);
        perror("open()");
        return(-1);
    }

    fprintf(stderr, "WRITE %s %s %d\n", path, ctrl, ctrl_size);
    while (ctrl_size > 0) {
        if ((wr = write(fd, ctrl, ctrl_size)) < 0) {
            perror("write");
            close(fd);
            return(-2);
        }

        ctrl_size -= wr;
        ctrl += wr;
    }

    close(fd);

    return(0);
}

/*
 * Write to "cgroup/task" file specified pid.
 * (Aka. Move proces with specified pid to specified group.
 */
static int __cgroup_task (const char *cgroup,
                          int pid)
{
    char buffer[16];
    int n;
    n = snprintf(buffer, sizeof(buffer), "%d", pid);
    return(__cgroup_write(cgroup, "tasks", buffer, n));
}

/*
 * Write to "cgroup/cgroup.event_control" the specified ctrl string.
 */
static int __cgroup_event_control (const char *cgroup,
                                   const char *ctrl,
                                   size_t ctrl_size)
{
    return(__cgroup_write(cgroup, "cgroup.event_control", ctrl, ctrl_size));
}

/*
 * Initialize cgroup control data structure, opening "cgroup/file".
 */
int __cgroup_ctrl_init (cgroup_ctrl_t *cgroup_ctrl,
                        const char *cgroup,
                        const char *file)
{
    char path[PATH_MAX];

    snprintf(path, PATH_MAX, "%s/%s", cgroup, file);
    if ((cgroup_ctrl->fd = open(path, O_RDONLY)) < 0) {
        fprintf(stderr, "%s\n", path);
        perror("open()");
        return(-1);
    }

    if ((cgroup_ctrl->efd = eventfd(0, EFD_NONBLOCK)) < 0) {
        perror("eventfd()");
        close(cgroup_ctrl->fd);
        return(-2);
    }

    fprintf(stderr, "READ %d %s\n", cgroup_ctrl->fd, path);
    return(0);
}

/*
 * Close cgroup control data structure.
 */
int cgroup_ctrl_close (cgroup_ctrl_t *cgroup_ctrl) {
    close(cgroup_ctrl->efd);
    close(cgroup_ctrl->fd);
    return(0);
}

/*
 * Initialize a cgroup control to listen on memory usage
 * with specified threshold.
 */
int cgroup_memory_threshold (cgroup_ctrl_t *cgroup_ctrl,
                             const char *cgroup,
                             uint64_t threshold)
{
    char buffer[64];
    int n;

    if (__cgroup_ctrl_init(cgroup_ctrl, cgroup, "memory.usage_in_bytes") < 0)
        return(-1);

    n = snprintf(buffer, sizeof(buffer), "%d %d %"PRIu64"",
                 cgroup_ctrl->efd, cgroup_ctrl->fd, threshold);
    if (__cgroup_event_control(cgroup, buffer, n) < 0) {
        cgroup_ctrl_close(cgroup_ctrl);
        return(-2);
    }

    return(0);
}

/*
 * Helper method to add cgroup control to epoll.
 */
static int __epoll_add (int epfd, cgroup_ctrl_t *cgroup_ctrl) {
    struct epoll_event ev;
    ev.events = EPOLLIN;
    ev.data.fd = cgroup_ctrl->efd;
    return(epoll_ctl(epfd, EPOLL_CTL_ADD, cgroup_ctrl->efd, &ev));
}

#define KB(x)                       ((x) * 1024)
#define MB(x)                       (KB((x) * 1024))
#define BLOB_SIZE                   KB(512)

static struct list *__alloc_next (struct list *head) {
    struct list *node;

    node = malloc(sizeof(struct list) +  BLOB_SIZE);
    node->next = head;
    memset(node->blob, 5, BLOB_SIZE);
    return(node);
}

static struct list *__free_mem (struct list *head, unsigned int nodes) {
    unsigned int i;
    struct list *t;

    if (!nodes) {
        while (head != NULL) {
            t = head->next;
            free(t);
            head = t;
        }
    } else {
        for (i = 0; i < nodes; ++i) {
            t = head->next;

            free(head);
            if ((head = t) == NULL)
                break;
        }
    }

    return(head);
}

static void __play_with_mem (struct list *head) {
    unsigned int i;
    struct list *p;

    for (p = head; p != NULL; p = p->next) {
        for (i = 0; i < BLOB_SIZE; ++i)
            p->blob[i] = (p->blob[i] + 64) >> 1;
    }
}

int main (int argc, char **argv) {
    struct epoll_event events[2];
    cgroup_ctrl_t cgroup_ctrl[2];
    struct list *mem = NULL;
    unsigned int tloop = 2;
    int nfds, i;
    uint64_t r;
    int epfd;

    if (argc < 2) {
        printf("Usage: cgroup-mem-threshold <cgroup>\n");
        return(1);
    }

    /* Move this process to specified cgroup */
    __cgroup_task(argv[1], getpid());

    /* Initialize epoll */
    if ((epfd = epoll_create(2)) < 0) {
        perror("epoll_create()");
        return(-1);
    }

    /* Setup a mem threshold notifier at 6M */
    cgroup_memory_threshold(&(cgroup_ctrl[0]), argv[1], MB(6));
    __epoll_add(epfd, &(cgroup_ctrl[0]));

    /* Setup a mem threshold notifier at 12M */
    cgroup_memory_threshold(&(cgroup_ctrl[1]), argv[1], MB(12));
    __epoll_add(epfd, &(cgroup_ctrl[1]));

    while (1) {
        if ((nfds = epoll_wait(epfd, events, 2, 1000)) < 0) {
            perror("epoll_wait()");
            break;
        }

        /* Check for memory notification */
        for (i = 0; i < nfds; ++i) {
            printf("Event %d %d\n", i, events[i].data.fd);
            if (events[i].data.fd == cgroup_ctrl[0].efd) {
                read(cgroup_ctrl[0].efd, &r, sizeof(uint64_t));
                printf("Mem Threshold 6M Notification %"PRIu64"\n", r);
            }  else if (events[i].data.fd == cgroup_ctrl[1].efd) {
                read(cgroup_ctrl[1].efd, &r, sizeof(uint64_t));
                printf("Mem Threshold 12M Notification %"PRIu64"\n", r);

                if (--tloop > 0)
                    mem = __free_mem(mem, tloop);
            }
        }

        /* Allocate some momory */
        mem = __alloc_next(mem);
        __play_with_mem(mem);
    }

    __free_mem(mem, 0);
    close(epfd);
    cgroup_ctrl_close(&(cgroup_ctrl[0]));
    cgroup_ctrl_close(&(cgroup_ctrl[1]));

    return(0);
}

class A {
private:
	static const int i; // 注意必须是静态的！ 
public:
	A() {}
};

const int A::i = 3;

class A {
private:
	const int a, b;
public:
	A() :a(1), b(2) {}
};

#include <iostream>
#include <vector>
using namespace std;

struct node {
	int data;
	node *left, *right;
};

void insert(node*& root, int data) {
	if (root == NULL) {
		root = new node;
		root->data = data;
		root->left = root->right = NULL;
		return;
	}
	if (data < root->data) {
		insert(root->left, data);
	}
	else {
		insert(root->right, data);
	}
}

void inOrderTraverse(const node* root, vector<int>& vi) {
	if (root == NULL) {
		return;
	}
	inOrderTraverse(root->left, vi);
	vi.push_back(root->data);
	inOrderTraverse(root->right, vi);
}

int main() {
	node* root = NULL;
	insert(root, 4);
	insert(root, 2);
	insert(root, 1);
	insert(root, 3);
	insert(root, 6);
	insert(root, 5);
	insert(root, 7);

	vector<int> in;
	inOrderTraverse(root, in);

	for (auto val : in) {
		cout << val << " ";
	}
	cout << endl;
	// 1 2 3 4 5 6 7
	return 0;
}

/*
 Sample code from https://www.redblobgames.com/pathfinding/a-star/
 Copyright 2014 Red Blob Games <redblobgames@gmail.com>
 
 Feel free to use this code in your own projects, including commercial projects
 License: Apache v2.0 <http://www.apache.org/licenses/LICENSE-2.0.html>
*/

#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <vector>
#include <utility>
#include <queue>
#include <tuple>
#include <algorithm>
#include <cstdlib>

struct SimpleGraph {
  std::unordered_map<char, std::vector<char> > edges;

  std::vector<char> neighbors(char id) {
    return edges[id];
  }
};

SimpleGraph example_graph {{
    {'A', {'B'}},
    {'B', {'A', 'C', 'D'}},
    {'C', {'A'}},
    {'D', {'E', 'A'}},
    {'E', {'B'}}
  }};

struct GridLocation {
  int x, y;
};

namespace std {
/* implement hash function so we can put GridLocation into an unordered_set */
template <> struct hash<GridLocation> {
  typedef GridLocation argument_type;
  typedef std::size_t result_type;
  std::size_t operator()(const GridLocation& id) const noexcept {
    return std::hash<int>()(id.x ^ (id.y << 4));
  }
};
}


struct SquareGrid {
  static std::array<GridLocation, 4> DIRS;

  int width, height;
  std::unordered_set<GridLocation> walls;

  SquareGrid(int width_, int height_)
     : width(width_), height(height_) {}

  bool in_bounds(GridLocation id) const {
    return 0 <= id.x && id.x < width
        && 0 <= id.y && id.y < height;
  }

  bool passable(GridLocation id) const {
    return walls.find(id) == walls.end();
  }

  std::vector<GridLocation> neighbors(GridLocation id) const {
    std::vector<GridLocation> results;

    for (GridLocation dir : DIRS) {
      GridLocation next{id.x + dir.x, id.y + dir.y};
      if (in_bounds(next) && passable(next)) {
        results.push_back(next);
      }
    }

    if ((id.x + id.y) % 2 == 0) {
      // aesthetic improvement on square grids
      std::reverse(results.begin(), results.end());
    }

    return results;
  }
};

std::array<GridLocation, 4> SquareGrid::DIRS =
  {GridLocation{1, 0}, GridLocation{0, -1}, GridLocation{-1, 0}, GridLocation{0, 1}};

// Helpers for GridLocation

bool operator == (GridLocation a, GridLocation b) {
  return a.x == b.x && a.y == b.y;
}

bool operator != (GridLocation a, GridLocation b) {
  return !(a == b);
}

bool operator < (GridLocation a, GridLocation b) {
  return std::tie(a.x, a.y) < std::tie(b.x, b.y);
}

std::basic_iostream<char>::basic_ostream& operator<<(std::basic_iostream<char>::basic_ostream& out, const GridLocation& loc) {
  out << '(' << loc.x << ',' << loc.y << ')';
  return out;
}

// This outputs a grid. Pass in a distances map if you want to print
// the distances, or pass in a point_to map if you want to print
// arrows that point to the parent location, or pass in a path vector
// if you want to draw the path.
template<class Graph>
void draw_grid(const Graph& graph, int field_width,
               std::unordered_map<GridLocation, double>* distances=nullptr,
               std::unordered_map<GridLocation, GridLocation>* point_to=nullptr,
               std::vector<GridLocation>* path=nullptr) {
  for (int y = 0; y != graph.height; ++y) {
    for (int x = 0; x != graph.width; ++x) {
      GridLocation id {x, y};
      std::cout << std::left << std::setw(field_width);
      if (graph.walls.find(id) != graph.walls.end()) {
        std::cout << std::string(field_width, '#');
      } else if (point_to != nullptr && point_to->count(id)) {
        GridLocation next = (*point_to)[id];
        if (next.x == x + 1) { std::cout << "> "; }
        else if (next.x == x - 1) { std::cout << "< "; }
        else if (next.y == y + 1) { std::cout << "v "; }
        else if (next.y == y - 1) { std::cout << "^ "; }
        else { std::cout << "* "; }
      } else if (distances != nullptr && distances->count(id)) {
        std::cout << (*distances)[id];
      } else if (path != nullptr && find(path->begin(), path->end(), id) != path->end()) {
        std::cout << '@';
      } else {
        std::cout << '.';
      }
    }
    std::cout << '\n';
  }
}

void add_rect(SquareGrid& grid, int x1, int y1, int x2, int y2) {
  for (int x = x1; x < x2; ++x) {
    for (int y = y1; y < y2; ++y) {
      grid.walls.insert(GridLocation{x, y});
    }
  }
}

SquareGrid make_diagram1() {
  SquareGrid grid(30, 15);
  add_rect(grid, 3, 3, 5, 12);
  add_rect(grid, 13, 4, 15, 15);
  add_rect(grid, 21, 0, 23, 7);
  add_rect(grid, 23, 5, 26, 7);
  return grid;
}

struct GridWithWeights: SquareGrid {
  std::unordered_set<GridLocation> forests;
  GridWithWeights(int w, int h): SquareGrid(w, h) {}
  double cost(GridLocation from_node, GridLocation to_node) const {
    return forests.find(to_node) != forests.end()? 5 : 1;
  }
};

GridWithWeights make_diagram4() {
  GridWithWeights grid(10, 10);
  add_rect(grid, 1, 7, 4, 9);
  typedef GridLocation L;
  grid.forests = std::unordered_set<GridLocation> {
    L{3, 4}, L{3, 5}, L{4, 1}, L{4, 2},
    L{4, 3}, L{4, 4}, L{4, 5}, L{4, 6},
    L{4, 7}, L{4, 8}, L{5, 1}, L{5, 2},
    L{5, 3}, L{5, 4}, L{5, 5}, L{5, 6},
    L{5, 7}, L{5, 8}, L{6, 2}, L{6, 3},
    L{6, 4}, L{6, 5}, L{6, 6}, L{6, 7},
    L{7, 3}, L{7, 4}, L{7, 5}
  };
  return grid;
}

template<typename T, typename priority_t>
struct PriorityQueue {
  typedef std::pair<priority_t, T> PQElement;
  std::priority_queue<PQElement, std::vector<PQElement>,
                 std::greater<PQElement>> elements;

  inline bool empty() const {
     return elements.empty();
  }

  inline void put(T item, priority_t priority) {
    elements.emplace(priority, item);
  }

  T get() {
    T best_item = elements.top().second;
    elements.pop();
    return best_item;
  }
};

template<typename Location, typename Graph>
void dijkstra_search
  (Graph graph,
   Location start,
   Location goal,
   std::unordered_map<Location, Location>& came_from,
   std::unordered_map<Location, double>& cost_so_far)
{
  PriorityQueue<Location, double> frontier;
  frontier.put(start, 0);

  came_from[start] = start;
  cost_so_far[start] = 0;
  
  while (!frontier.empty()) {
    Location current = frontier.get();

    if (current == goal) {
      break;
    }

    for (Location next : graph.neighbors(current)) {
      double new_cost = cost_so_far[current] + graph.cost(current, next);
      if (cost_so_far.find(next) == cost_so_far.end()
          || new_cost < cost_so_far[next]) {
        cost_so_far[next] = new_cost;
        came_from[next] = current;
        frontier.put(next, new_cost);
      }
    }
  }
}

template<typename Location>
std::vector<Location> reconstruct_path(
   Location start, Location goal,
   std::unordered_map<Location, Location> came_from
) {
  std::vector<Location> path;
  Location current = goal;
  while (current != start) {
    path.push_back(current);
    current = came_from[current];
  }
  path.push_back(start); // optional
  std::reverse(path.begin(), path.end());
  return path;
}

inline double heuristic(GridLocation a, GridLocation b) {
  return std::abs(a.x - b.x) + std::abs(a.y - b.y);
}

template<typename Location, typename Graph>
void a_star_search
  (Graph graph,
   Location start,
   Location goal,
   std::unordered_map<Location, Location>& came_from,
   std::unordered_map<Location, double>& cost_so_far)
{
  PriorityQueue<Location, double> frontier;
  frontier.put(start, 0);

  came_from[start] = start;
  cost_so_far[start] = 0;
  
  while (!frontier.empty()) {
    Location current = frontier.get();

    if (current == goal) {
      break;
    }

    for (Location next : graph.neighbors(current)) {
      double new_cost = cost_so_far[current] + graph.cost(current, next);
      if (cost_so_far.find(next) == cost_so_far.end()
          || new_cost < cost_so_far[next]) {
        cost_so_far[next] = new_cost;
        double priority = new_cost + heuristic(next, goal);
        frontier.put(next, priority);
        came_from[next] = current;
      }
    }
  }
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 100;
char A[N], B[N];
int dp[N][N];

int main() {
	int n;
	cin >> A + 1;	// Start from index 1
	cin >> B + 1;
	int lenA = strlen(A + 1);
	int lenB = strlen(B + 1);
	// boundary
	for (int i = 0; i <= lenA; i++) {
		dp[i][0] = 0;
	}
	for (int j = 0; j <= lenB; j++) {
		dp[0][j] = 0;
	}
	// state transition equation
	for (int i = 1; i <= lenA; i++) {
		for (int j = 1; j <= lenB; j++) {
			if (A[i] == B[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	cout << dp[lenA][lenB] << endl;
	return 0;
}

/*
Sample Input：
sadstory
adminsorry
Sample Output:
6
*/

//1
#include<string>
char str[1000];
cin.getline(str, 1000);
int len=strlen(str);
//2
#include<string>
string s;
getline(cin,s);
int len=s.size();
//3
do:scanf("%c",c) while(c!='\n')
//4 gets()在C11标准中被删除