Pagini recente » Cod sursa (job #3131277) | Cod sursa (job #467250) | Cod sursa (job #3002158) | Cod sursa (job #1316408) | Cod sursa (job #2278363)
//
// main.cpp
// potrivirea_sirurilor
//
// Created by Tereza Oprea on 07/11/2018.
// Copyright © 2018 Tereza Oprea. All rights reserved.
//
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
char pattern[2000010], text[2000010];
int d[2000010], t[2000010], i, j;
unsigned long n1, n2;
int ans, v[20000010];
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int main() {
fin.getline(pattern, 2000010);
fin.getline(text, 2000010);
i = 0; j = 1;
n1 = strlen (pattern);
n2 = strlen (text);
while (j<n1){
if ( pattern[i] == pattern[j]){
d[j] = i+1;
i++;
j++;
continue;
}
if ( i == 0 ){
j++;
continue;
}
i = d[i-1];
}
i = 0; j = 0;
int lun = 0;
while (j < n2){
if (pattern[i] == text[j]){
lun++;
if (lun == n1){
ans++;
v[ans] = j - n1 + 1;
i = d[n1-1];
lun = i;
j++;
continue;
}
i++;
j++;
continue;
}
if (i == 0){
lun = 0;
j++;
continue;
}
i = d[i-1];
lun = i;
}
fout << ans << '\n';
for (i = 1; i<=ans; i++)
fout << v[i] << ' ';
return 0;
}