Cod sursa(job #1679870)

Utilizator BrandonChris Luntraru Brandon Data 8 aprilie 2016 12:13:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.95 kb
///Rabin-Karp
/*#include <fstream>
#include <string>

#define NMAX 2000005
#define BASE 101
#define MOD1 100007
#define MOD2 100021
using namespace std;

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

string A, B;

int hash1_A, hash2_A, hash1_B, hash2_B, reh_base1, reh_base2, ans_nr;
bool match[NMAX];

int main() {
    cin >> A;
    cin >> B;

    if(A.size() > B.size()) {
        cout << 0 << '\n';
        return 0;
    }

    reh_base1 = reh_base2 = 1;

    for(int i = 0; i < (int) A.size(); ++i) {
        hash1_A = (hash1_A * BASE + A[i]) % MOD1;
        hash2_A = (hash2_A * BASE + A[i]) % MOD2;

        if(i) {
            reh_base1 = (reh_base1 * BASE) % MOD1;
            reh_base2 = (reh_base2 * BASE) % MOD2;
        }
    }

    for(int i = 0; i < (int) A.size(); ++i) {
        hash1_B = (hash1_B * BASE + B[i]) % MOD1;
        hash2_B = (hash2_B * BASE + B[i]) % MOD2;
    }


    if(hash1_A == hash1_B and hash2_A == hash2_B) {
        match[0] = true;
        ++ans_nr;
    }

    for(int i = (int) A.size(); i < (int) B.size(); ++i) {
        hash1_B = hash1_B - (B[i - A.size()] * reh_base1) % MOD1 + MOD1;
        hash1_B = (hash1_B * BASE + B[i]) % MOD1;

        hash2_B = hash2_B - (B[i - A.size()] * reh_base2) % MOD2 + MOD2;
        hash2_B = (hash2_B * BASE + B[i]) % MOD2;

        if(hash1_A == hash1_B and hash2_A == hash2_B) {
            match[i - A.size() + 1] = true;
            ++ans_nr;
        }
    }

    cout << ans_nr << '\n';
    ans_nr = min(ans_nr, 1000);

    for(int i = 0; i < (int) B.size() and ans_nr; ++i) {
        if(!match[i]) {
            continue;
        }

        --ans_nr;
        cout << i << ' ';
    }

    cout << '\n';
    return 0;
}
*/
///KMP
/*#include <fstream>
#include <string>
#include <vector>

using namespace std;

const int MaxLng = 2000005;

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

vector <int> ans;
string A, B;

int pref[MaxLng];
int k;

int main() {
  string str;

  cin >> str;
  A.push_back('0');
  A += str;

  cin >> str;
  B.push_back('0');
  B += str;

  for(int i = 2; i <= (int) A.size() - 1; ++i) {
    k = pref[i - 1];

    while(k and A[k + 1] != A[i]) {
      k = pref[k];
    }

    if(A[k + 1] == A[i]) {
      ++k;
    }

    pref[i] = k;
  }

  k = 0;

  for(int i = 1; i <= (int) B.size() - 1; ++i) {
    while(k and A[k + 1] != B[i]) {
      k = pref[k];
    }

    if(A[k + 1] == B[i]) {
      ++k;
    }

    if(k == (int) A.size() - 1 and ans.size() < 1000) {
      ans.push_back(i - (A.size() - 1));
    }
  }

  cout << ans.size() << '\n';

  for(auto it: ans) {
    cout << it << ' ';
  }

  return 0;
}*/
#include<string.h>
#include<cstdio>
using namespace std;

char a[2000002];
char b[2000002];
int pref[2000001];
int rasp[2000001];
int k;

int main(){
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    int n=1,m=1,i,pot;
    scanf ("%s\n",&a);
    scanf ("%s",&b);
    n=strlen(a);
    m=strlen(b);
    for(i=n;i>0;i--) a[i]=a[i-1];
    for(i=m;i>0;i--) b[i]=b[i-1];

    //pref[i]= lungimea celui mai lung prefix al lui a, de lungime <i, care incepe in b[1], b[2] ... b[i]
    pref[1]=0;
    for(i=2;i<=n;i++){
        k=pref[i-1];
        while(k>0 &&a[k+1]!=a[i])
            k=pref[k];
        if (a[k+1]==a[i]) k++;
        pref[i]=k;
        //printf ("%d\n",pref[i]);
    }


    k=0;
    pot=0;
    for(i=1;i<=m;i++){
        //printf ("%d\n",pot);
        while(pot>0 &&a[pot+1]!=b[i])
            pot=pref[pot];
        //printf ("%d\n",pot);
        if (a[pot+1]==b[i])
            pot++;
        //printf ("%d\n",pot);
        if (pot==n){
            k++;
            rasp[k]=i-n;
        }
        //printf ("%d\n",pot);
    }

    printf ("%d\n",k);
    if (k>1000) k=1000;
    for(i=1;i<=k;i++)
        printf ("%d ",rasp[i]);
    return 0;
}