Mai intai trebuie sa te autentifici.
Cod sursa(job #1856163)
| Utilizator | Data | 24 ianuarie 2017 16:42:47 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.8 kb |
#include <bits/stdc++.h>
using namespace std;
char str[(int)4e6 + 10];
int z[sizeof(str)] = {} ;
void build_z(const int n){
for(int i = 1, mij = 0, dr = 0; i < n; ++i){
int j = (dr < i ? 0 : min(z[i-mij], dr-i+1));
while(str[i+j] == str[j]) ++j;
z[i] = j;
if(i+j-1 > dr) mij = i, dr = i+j-1; } }
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> str;
const int n = strlen(str);
f >> (str+n+1);
const int m = strlen(str+n+1);
str[n] = '#';
build_z(n+m+1);
int rez = 0;
vector<int> pozs;
for(int i = 0; i < m; ++i){
if(z[n+i+1] == n){
++rez;
if(pozs.size() < 1000) pozs.push_back(i); } }
g << rez << '\n';
for(const auto x : pozs){
g << x << ' '; }
return 0; }
