Cod sursa(job #997963)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 15 septembrie 2013 12:38:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int knmax = 2e6 + 6;

char a[knmax], b[knmax];
int l1, l2;

void read(){
  gets(a);
  gets(b);
  l1 = strlen(a);

  for(int i = l1; i > 0; --i)
    a[i] = a[i - 1];

  l2 = strlen(b);

  for(int i = l2; i > 0; --i)
    b[i] = b[i - 1];

  a[0] = '*';
  b[0] = '$';
}

int t[knmax];

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

int nrsol, sol[knmax];
vector<int> ans;

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

  read();

  if(l1 > l2){
    printf("0");
    return 0;
  }

  prefix();

  for(int i = 1; i <= l2; ++i){
    int p = sol[i - 1];
    if(b[i] == a[p + 1])
      sol[i] = p + 1;
    else
      do{
        p = t[p];
        if(b[i] == a[p + 1]){
          sol[i] = p + 1;
          break;
        }
      }while(p);
    if(sol[i] == l1){
      ++nrsol;
      if(nrsol <= 1000)
        ans.push_back(i - l1);
    }
  }

  printf("%d\n", nrsol);

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

  return 0;
}