Cod sursa(job #2061356)

Utilizator netfreeAndrei Muntean netfree Data 9 noiembrie 2017 09:42:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");

const int N_MAX = 2000000 + 5;

int f[N_MAX];

void build_f(string pattern)
{
  int m = pattern.size(), i, j;

  f[0] = f[1] = 0;

  for(i = 2; i <= m; i++) {
    j = f[i - 1];
    for( ; ; ) {
      if(pattern[j] == pattern[i - 1]) {
        f[i] = j + 1; break;
      }
      if(j == 0) {
        f[i] = 0;
        break;
      }

      j = f[j];
    }
  }
}

vector <int> ans;

void kmp(string text, string pattern)
{
    int n = text.size(), m = pattern.size(), i, j;

  build_f(pattern);

  i = 0, j = 0;

  for( ; ; ) {
    if(j == n) break;

    if(text[j] == pattern[i]) {
      i++;
      j++;
      if(i == m)
        ans.push_back(j-m);
    }

    else if(i > 0)
        i = f[i];

    else j++;
  }
}

string text, pattern;

int main()
{
    fin >> pattern >> text;

    kmp(text, pattern);

    fout << ans.size() << "\n";

    for(auto i : ans)
        fout << i << " ";

    return 0;
}