Cod sursa(job #1673207)

Utilizator lflorin29Florin Laiu lflorin29 Data 3 aprilie 2016 15:52:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000007;

int N, M, pi[MAXN];
vector<int>match;
char A[MAXN], B[MAXN];

void makepi()
{
   pi[1] = 0;
   for(int i = 2, q = 0; i <= N; ++i)
   {
      while(q && A[q + 1] != A[i])
           q = pi[q];
      if(A[q + 1] == A[i]) ++q;
      pi[i] = q;
   }
}

void find_matches()
{
   int q(0);
   for(int i = 1; i <= M; ++i)
   {
      while(q && A[q + 1] != B[i])
          q = pi[q];
      if(A[q + 1] == B[i]) ++q;

      if(q == N)
      {
         if(match.size() + 1 <= 1000)
            match.push_back(i - N + 1);
         q = pi[q];
      }
   }
}

void print(ofstream &cout)
{
   cout << match.size() << '\n';
   for(auto itr : match)
      cout << itr - 1 << ' ';
}

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

   cin >> (A + 1) >> (B + 1);
   N = strlen(A + 1), M = strlen(B + 1);

   makepi();
   find_matches();
   print(cout);
   return 0;
}