Cod sursa(job #3202208)

Utilizator timicsIoana Tamas timics Data 11 februarie 2024 05:35:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
#define Nmax 1000100
#define LMax 40
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;

string s1,s2;
int cnt = 0;

class Kmp {
private:
  vi nx;
public:
  Kmp(string &s1) {
    nx.resize(sz(s1));
    int k = -1; nx[0] = -1;
    rep(i,1,sz(s1)) {
      while(k >= 0 && s1[k+1] != s1[i]) k = nx[k];
      if(s1[k+1] == s1[i]) ++k;
      nx[i] = k;
    } 
  }

  vi match(string &s1, string &s2) {
    vi ret;
    int k=-1;
    for(int i=0;i<sz(s2);++i) {
      while(k >= 0 && s1[k+1] != s2[i]) k = nx[k];
      if(s1[k+1] == s2[i]) ++k; 
      if(k==sz(s1)-1) {
        k = nx[k];
        ++cnt;
        if(ret.size() < 1000) ret.pb(i-sz(s1)+1);
      }
    }
    return ret;
  }
};


int main() {
  ifstream fin; fin.open ("strmatch.in");
  ofstream fout; fout.open ("strmatch.out");
  fin>>s1>>s2;
  Kmp k(s1);
  vi m = k.match(s1,s2);
  fout<<cnt<<"\n";
  for(auto x: m) {
    fout<<x<<" ";
  }
  return 0;
}