Cod sursa(job #1163620)

Utilizator thebest001Neagu Rares Florian thebest001 Data 1 aprilie 2014 15:18:54
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define MAX 2000001
char A[MAX], B[MAX];
int prefix[MAX], s[MAX];
int al,sn;
void make_prefix(){
  int k=0;
  al=1;
  for (int i=2;A[i];i++) {
    al++;
    while (k>0 && A[k+1]!=A[i])
      k=prefix[k];
    if (A[k+1]==A[i])
      k++;
    prefix[i]=k;
  }
}
int main(){
  in.getline(A + 1, MAX);
  in.getline(B + 1, MAX);
  make_prefix();
  int k=0;
  for (int i=2;B[i];i++) {
    while (k>0 && A[k+1]!=B[i])
      k=prefix[k];
    if (A[k+1]==B[i])
      k++;
    if (k==al)
      s[++sn]=i-al;
  }
  out<<sn<<"\n";
  if (sn>1000) sn=1000;
  for (int i=1;i<=sn;i++)
    out<<s[i]<<" ";
  out<<"\n";
  return 0;
}