Cod sursa(job #1585566)

Utilizator preda.andreiPreda Andrei preda.andrei Data 31 ianuarie 2016 11:17:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

void change(char s[], int len);
void prefix(char s[], int pre[], int len);

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    char word[100005];
    char str[100005];

    int pre[100005];
    int positions[1001];

    int lenw, lens, k, ind = 0;

    fin.getline(word, 100000);
    fin.getline(str, 100000);

    lenw = strlen(word);
    lens = strlen(str);
    change(word, lenw);
    change(str, lens);

    prefix(word, pre, lenw);

    k = 0;
    for(int i=1; i<=lens; ++i){
      while(k > 0 && str[i] != word[k+1])
        k = pre[k];

      if(str[i] ==  word[k+1])
        k++;

      if(k == lenw){
        ind++;
        if(ind <= 1000)
          positions[ind] = i - lenw;
      }
    }

    fout << ind << "\n";
    for(int i=1; i<=ind && i<=1000; ++i)
      fout << positions[i] << " ";

    return 0;
}

void prefix(char s[], int pre[], int len){
  int k = 0;

  pre[1] = 0;
  for(int i=2; i<=len; ++i){
    while(k > 0 && s[i] != s[k+1])
      k = pre[k];
    if(s[i] == s[k+1])
      k++;
    pre[i] = k;
  }
}

void change(char s[], int len){
  for(int i=len; i>0; --i)
    s[i] = s[i-1];
  s[len+1] = '\0';
}