Cod sursa(job #3334336)

Utilizator ragonuldefocNes Damian Calin ragonuldefoc Data 17 ianuarie 2026 11:08:37
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("strmatch.in");
ofstream c("strmatch.out");

#define maxn 2000001

char pattern[maxn], text[maxn];
int pref[maxn], n, m, maxSolNr;
vector <int> sol;

void compute_prefix_table() {

  int k;
	for(int i = 2; i <= n; i++) {
    k = pref[i-1];

    while(k && pattern[i] != pattern[k+1]) {
      k = pref[k];
    }

    if(pattern[i] == pattern[k+1]) {
      k ++;
    }

    pref[i] = k;
  }
}

int main() {
  int j;

  f>>pattern+1>>text+1;

  n = strlen(pattern+1);
  m = strlen(text+1);

  compute_prefix_table();

  j = 0;
  for(int i = 1; i <= m; i++) {
    while(j && text[i] != pattern[j+1]) {
      j = pref[j];
    }
    if(text[i] == pattern[j+1]) {
      j++;
    }

    if(j == n)
    {
      sol.push_back(i - n + 1);
    }

  }


  c<<sol.size()<<'\n';
  maxSolNr = 0;
  for(auto it:sol) {
    c<<it-1<<' ';
    if(++maxSolNr == 1000)
      break;
  }

  return 0;
}