Cod sursa(job #1681558)

Utilizator BrandonChris Luntraru Brandon Data 9 aprilie 2016 16:19:12
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
///Z Algorithm
#include <fstream>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

const int MaxLng = 2000005;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

vector <int> ans;

string A, B;

int Z[MaxLng], Z_sr[MaxLng];
int szA, szB, last, ans_nr;

int main() {
  cin >> A;
  szA = (int) A.size();
  A = '0' + A;

  cin >> B;
  szB = (int) B.size();
  B = '0' + B;

  last = 0;

  for(int i = 2; i <= szA; ++i) {
    if(last + Z_sr[last] > i) {
      Z_sr[i] = min(Z_sr[i - last + 1], last + Z_sr[last] - i);
    }

    while(i + Z_sr[i] < szA and A[i + Z_sr[i]] == A[Z_sr[i] + 1]) {
      ++Z_sr[i];
    }

    if(i + Z_sr[i] > last + Z_sr[last]) {
      last = i + Z_sr[i];
    }
  }

  last = 0;

  for(int i = 1; i <= szB; ++i) {
    if(last + Z[last] > i) {
      Z[i] = min(Z_sr[i - last + 1], last + Z[last] - i); ///i - last + 1 = correspondent of i in pattern; last + Z[last] - i = distance from i to end of generated path
    }

    while(Z[i] < szA and i + Z[i] < szB and A[Z[i] + 1] == B[i + Z[i]]) {
      ++Z[i];
    }

    if(i + Z[i] > last + Z[last]) {
      last = i;
    }

    if(Z[i] == szA) {
      ++ans_nr;

      if(ans_nr <= 1000) {
        ans.push_back(i);
      }
    }
  }

  cout << ans_nr << '\n';

  for(auto it: ans) {
    cout << it - 1 << ' ';
  }
  return 0;
}