Cod sursa(job #1795905)

Utilizator ade_tomiEnache Adelina ade_tomi Data 2 noiembrie 2016 22:22:49
Problema Potrivirea sirurilor Scor 22
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000009
using namespace std;
string s1,s2;
char a[NMAX], b[NMAX], pi[NMAX];
int m, n;
vector <int> sol;
int main ()
{
    ifstream cin ("strmatch.in");
    ofstream cout ("strmatch.out");
    cin >> s1 >> s2;
   // n = strlen (a + 1);
    for (int i = 0; i < s1.size(); i++)
    {
        n++;
        a[n] = s1[i];
    }
    for (int i = 0; i < s2.size(); i++)
    {
        m++;
        b[m] = s2[i];
    }
    //m = strlen (b + 1);
    //cout << n << m;
    pi[1] = 0;
    int k = 0;
    for (int i = 2; i <= n; i++)
    {
        while (k && a[k + 1] != a[i])
            k = pi[k];
        if (a[k + 1] == a[i])
            k++;
        pi[i] = k;
    }
    k = 0;
    int ss = 0;
    for (int i = 1; i <= m; i++)
    {
        while (k && a[k + 1] != b[i])
            k = pi[k];
        if (a[k + 1] == b[i])
            k ++;
        if (k == n && sol.size() <= 1000)
            sol.push_back (i - k);
        if (k == n){
            ss++;
            k = pi[k];
        }
    }
    cout << ss  << "\n";
    for (int i = 0; i < sol.size(); i++)
        cout  <<  sol[i] << " " ;
    return 0;
}