Cod sursa(job #930099)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 27 martie 2013 13:54:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<cstdio>
#include<cassert>
#include<cstring>

#include<vector>
#include<algorithm>

using namespace std;

int len1, len2;
char a[2000005], b[2000005];

void read(){
  assert(freopen("strmatch.in", "r", stdin));

  gets(a);
  gets(b);
  len1 = strlen(a);
  len2 = strlen(b);
  for(int i = len1; i > 0; --i)
    a[i] = a[i - 1];
  for(int i = len2; i > 0; --i)
    b[i] = b[i - 1];
}

int t[2000005];

void prefix(){
  t[1] = 0;
  for(int i = 2; i <= len1; ++i){
    int p = i - 1;
    do{
      p = t[p];
      if(a[i] == a[p + 1]){
        t[i] = p + 1;
        break;
      }
    }while(p);

  }

}

int matches, dp[2000005];
vector<int> ans;

void solve(){
  prefix();

  for(int i = 1; i <= len2; ++i){
    int p = dp[i - 1];

    if(a[p + 1] == b[i]){
      dp[i] = p + 1;
      continue;
    }

    do{
      p = t[p];
      if(b[i] == a[p + 1]){
        dp[i] = p + 1;
        break;
      }
    }while(p);

  }

  for(int i = 1; i <= len2; ++i)
    if(dp[i] == len1){
      ++matches;
      if(ans.size() < 1000)
        ans.push_back(i - len1);
    }
}

void write(){
  assert(freopen("strmatch.out", "w", stdout));

  printf("%d\n", matches);
  for(int i = 0; i < ans.size(); ++i)
    printf("%d ", ans[i]);
}

int main(){
  read();
  solve();
  write();

  return 0;
}