Cod sursa(job #1089647)

Utilizator cruelifanLouis Cypher cruelifan Data 21 ianuarie 2014 20:27:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

#define mp make_pair
#define pb push_back
#define f first
#define s second

using namespace std;

const int knmax = 2e6 + 5;

char a[knmax], b[knmax];
int sza, szb, t[knmax];

void get_pref(char *v){
  memset(t, 0, sizeof(t));
  t[0] = t[1] = 0;
  szb = strlen(v + 1);
  for(int i = 2; i <= szb; ++i){
    int p = i - 1;
    do{
      p = t[p];
      if(v[p + 1] == v[i]){
        t[i] = p + 1;
        break;
      }
    }while(p);
  }
}

int dp[knmax];

pair<int, vector<int> > first_1k_or_less(char *v, char *u){
  memset(dp, 0, sizeof(dp));
  sza = strlen(v + 1);
  get_pref(u);

  vector<int> ans;
  int many = 0;
  dp[0] = 0;
  for(int i = 1; i <= sza; ++i){
    int p = dp[i - 1];
    do{
      p = t[p];
      if(u[p + 1] == v[i]){
        dp[i] = p + 1;
        break;
      }
    }while(p);
    if(u[dp[i - 1] + 1] == v[i])
      dp[i] = dp[i - 1] + 1;
    if(dp[i] == szb){
      ++many;
      if(many <= 1000)
        ans.push_back(i - szb);
    }
  }

  return mp(many, ans);
}

int main(){
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  gets(b + 1);
  gets(a + 1);

  pair<int, vector<int> > ans = first_1k_or_less(a, b);

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

  return 0;
}