Pagini recente » Istoria paginii runda/oji-2015-cls11-12/clasament | Cod sursa (job #2220473) | Cod sursa (job #1495268)
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n , m , pi[NMAX] , dp[NMAX] , nr;
char s[NMAX] , c[NMAX];
int main()
{
f >> c + 1 >> s + 1;
n = strlen(s + 1);
m = strlen(c + 1);
pi[1] = 0;
for(int i = 2 ; i <= m ; ++i) {
int k = pi[i - 1];
while(k > 0 && c[i] != c[k + 1]) {
k = pi[k];
}
if(c[i] == c[k + 1]) {
pi[i] = k + 1;
}
else{
pi[i] = 0;
}
}
int k = 0;
for(int i = 1 ; i <= n ; ++i) {
while(k > 0 && s[i] != c[k + 1]) {
k = pi[k];
}
if(s[i] == c[k + 1]) {
++k;
}
dp[i] = k;
}
for(int i = 1 ; i <= n ; ++i) {
if(dp[i] == m) {
++nr;
}
}
g << nr << '\n';
nr = 0;
for(int i = 1 ; i <= n ; ++i) {
if(dp[i] == m) {
++nr;
g << i - m << " ";
}
if(nr >= 1000){
return 0;
}
}
return 0;
}