Cod sursa(job #1797114)

Utilizator mihai.alphamihai craciun mihai.alpha Data 3 noiembrie 2016 23:33:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;
const int NRMAX = 2000003;
int k, nrsol, p[NRMAX];
char a[NRMAX], b[NRMAX];

ifstream fin("strmatch.in");
ofstream g("strmatch.out");

vector <int> rez;
vector <int>::iterator it;
int main()  {
    int m, n;
    fin>>a+1;
    fin>>b+1;
    m = strlen(a+1);
    n = strlen(b+1);
    int i;
    for(i = 2;i <= m;i++)  {
        while(a[i] != a[k + 1] && k)
            k = p[k];
        if(a[i] == a[k+1])
            k++;
        p[i] = k;
    }
    k = 0;
    for(i = 1;i <= n;i++)  {
        while(b[i] != a[k + 1] && k)
            k = p[k];
        if(b[i] == a[k+1])
            k++;
        if(k == m)
            nrsol++;
        if(nrsol <= 1000 && k == m)
            rez.push_back(i - m);
    }
    g << nrsol << "\n";
    for(it = rez.begin();it < rez.end();it++)
        g << *it << " ";
    fin.close();
    g.close();
    return 0;
}