Cod sursa(job #2899870)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 9 mai 2022 12:59:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
/// always:
#include <cstdio>
#include <string>

/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

bool home = 1;
using namespace std;

const string TASKNAME="strmatch";


signed main() {
#ifdef INFOARENA
  home = 0;
#endif

  if(!home) {
    freopen((TASKNAME + ".in").c_str(), "r", stdin);
    freopen((TASKNAME + ".out").c_str(), "w", stdout);
  }else{
    freopen ("I_am_iron_man", "r", stdin);
  }

  string s, t;
  cin>>s>>t;
  int m=(int)s.size();
  int n=(int)t.size();
  vector<int> lp(m,0);
  int j=0;
  for (int i=1;i<m;i++) {
    while (j&&s[i]!=s[j]) j=lp[j-1];
    if (s[i]==s[j]) j++;

    lp[i]=j;
  }

  int sol=0;
  vector<int> inds;
  j=0;
  for (int i=0;i<n;i++) {
    while (j&&t[i]!=s[j]) j=lp[j-1];
    if (t[i]==s[j]) j++;

    if (j==m) {
      sol++;
      if(sol<=1000) inds.push_back(i-m+1);
      j=lp[j-1];
    }
  }
  cout<<sol<<"\n";
  for (auto &i:inds){
    cout<<i<<" ";
  }
  cout<<"\n";
}