Cod sursa(job #1464046)

Utilizator RuxyRezidentTMRuxandra P RuxyRezidentTM Data 22 iulie 2015 10:17:07
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char text[2000001], pattern[2000001];
vector<int> pos;
int n, m;
int lps[2000001];

void readInput() {

    f>>pattern>>text;
    m = strlen(text);
    n = strlen(pattern);

}

void lpsCreation() {
    lps[0] = 0;
    for(int i = 1; i < n; i++){
        if(pattern[i] == pattern [lps[i-1]])
            lps[i] = lps[i-1] + 1;
        else {
            if( lps[i-1] != 0)
                lps[i] = lps[i-1];
            else
                i++;
        }
    }
}

void kmp() {
    int i = 0, j = 0, occ = 0;
    pos = vector<int>();
    while(i < m) {

        if(text[i] == pattern[j]) {
            i++; j++;

        }
        if(j == n) {
               occ++;
               pos.push_back(i - j);
               j = lps[j-1];
            }
        else if (i< m && text[i] != pattern[j]) {
                if(j != 0) {
                    j = lps[j-1];
                }
                else {
                    i++;
                }

        }
    }
    g<<occ<<'\n';
    for(int i = 0; i < pos.size(); i++) {
        g << pos.at(i) << ' ';
    }

}


int main()
{
    readInput();
    lpsCreation();
    kmp();
    return 0;
}